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.