Look into Swords and Soldiers for sure. It's a 2D, side-scrolling RTS that's highly streamlined, but also pretty fun, especially in multiplayer (although the single player campaign alone can take you up to four hours to complete, not including the 1-player mini-games).
You seem to enjoy platformers. NyxQuest has been described as a much more fleshed-out and enjoyable Lost Winds. I've heard good things from everyone, although I haven't played it yet myself. Give it a look-see.
You seem to be a Final Fantasy fan: Final Fantasy IV: The After Years has been getting good feedback from fans of the original FF IV.
LiT is a pretty fun puzzle game: no falling blocks are involved, just a need to get from Point A to Point B without once falling into the darkness.
The Bit.Trip games are both pretty solid, if fiendishly difficult, "rhythm" games. The first is Pong From Hell, the second is harder to describe (and not as good).
Bonsai Barber. It's hard to describe, and doesn't look great in vids, but it's fun to actually play.
All of these are very good except LIT which I just didn't care for after about a dozen levels.
I'd also add: Rock 'N' Roll Climber if you have a BB: it looks awful (both graphically and perception of fun-wise) but there is something oddly addictive about it; Tales of Monkey Island which is somewhat marred by some technical issues, but is still quite fun; Ant Nation which is basically a stripped-down Pikmin with, well, ants; Neves Plus, an awesome continuation of the DS game (if you like brain-teasers this is a must own); Water Warfare, a nice little FPS that not nearly enough people play; Rainbow Islands Towering Adventure is a solid--and challenging--update to the arcade classic; and finally, Let's Catch (no, really) about as a Zen-like and relaxing as games get short of being Bonsai Barber.
The thing I like about WW games is that, on the whole, they seem to take more risks than Live or PSN titles, even when a lot of those risks don't pan out. (I imagine another consequence of low-def development making it cheaper and less risky, financially, to take a flier on bizarre concepts like simulating rock climbing and playing catch.)