How about this setting: The evil Rys has stolen all GPU power from your system and you have to get it back. So the goal of the game would be to re-enable your GPU features one by one.
When you start the world inside your GPU is black-and-white, flat shaded, non-textured, non-antialiased. After the first boss-battle you get back color. Then texturing, texture filtering, anti-aliasing, alpha-bleding, shadows, bump-mapping, etc. You get the idea.
I would plead for a single player game, a cross between System Shock and Tron. You, the hero, start with fixed-function weapons and skills. Later the fixed-function units will be upgraded to shaders. Once you got shaders installed you can upgrade your weapons and skills. The level of the shader system (1.0, 1.1., ..., 3.0, 4.0) determines how many weapons and skills you can carry and how powerful they can be.
Every level would have a primary objective. You need to accomplish this in order to get to the next level. So the player always knows what he is supposed to do. Then there may (or may not) be secondary objectives for every level. You may fulfill these objectives, but you can also ignore them. It's up to you. Secondary objectives may give you bonues such as advanced skills or weapons, or just a cutscene, or may alter the overall storyline, or you can get something like a familiar that helps you fight through the rest of the level. Additionally there are hidden objectives, like finding a secret place, solving a difficult puzzle. They give you nice bonuses such as increased shader slots, so you can store more shader weapons and skills. While you can review your primary and secondary objectives any time you like, hidden objectives are only displayed after you accomplished them.
The levels should not be strictly linear. There should be at least two ways through a level. The obvious and one that is harder to follow and may include some jumping action or various skills in order to advance. Likewise there should be two ways of playing through a level. The well-known shoot-everything-in-sight technique and the use-your-head way, which may include using skills and solving puzzles. It should be noted that these two threads through a level are not strictly separated, in fact they intersect once in a while. So if you're bored with solving a puzzle of lack the skill to advance, you change to run-and-gun and shoot your way through the level. Likewise when your ammo is running low or shooting bad guys is getting repetive, you can get through the level without so much shooting.
In order to spice things up and keep the player focused the levels occasionally should have time limits.
There are three levels of difficulty. N00b, Normal and GPU Whiz. On N00b level there are fewer and weaker enemies, more ammo, relaxed time limits, but no hidden objectives and fewer secondary objectives (in oder to motivate people to play a second time through on normal level). On normal level threre are more and stronger enemies, less ammo, tigher time limits and all secondary objectives. On GPU Whiz level you have the same number of enemies like on N00b level, but they are a bit stronger. Ammo is much more scarce, so you can't just gun your way through. Time limits are even tighter and there are more of them. Saving is limited to save points (but you are able to suspend/resume your game every time, so when you have to stop playing for a reason, you can pick up where you left). All secondary hidden objectives are available. Additionally to open doors and hack systems you may be required to write a short piece of code (no longer than say 10-15 lines) in a shader like language in order to solve some simple mathematical riddle (combined with a time limit that should provide some fun...).
A game like this could be educational and fun.
What do you guys think?