Robotek is pretty simple but super-addicting.
Canabalt is a must, especially since Danny B did the music.
Swords & Soldiers is a bunch of fun too.
Spectral Souls and Final Fantasy III are full console-quality games, but have prices to match.
There's also the remake of the first Final Fantasy.
There are a few apps that are for the most part impractical to play on your phone, but I have to mention them solely due to how awesome it is that they even exist:
GemRB lets you play Bioware's Infinity Engine games (i.e. Baldur's Gate, Icewind Dale, Planescape Torment). ON YOUR PHONE.
You can play Star Control 2. ON YOUR PHONE.
If you own and love any of those old-school point-and-click adventure games like Monkey Island, King's Quest, Day of the Tentacle, Sam & Max, you can play them with ScummVM. ON YOUR PHONE.
The sad thing is I don't have time for all these awesome apps because I waste all my time playing crappy Zynga games with my friends like Scramble, Words With Friends, and Draw Something.
And of course you can't show off your fancy Android phone without pointless live wallpapers like Pixel Zombies, Katamari, and Cave Story.
And if you're not Swyping, START SWYPING.
Thanks for posting this thread by the way, Flexstyle. Just installed two apps I'd never heard of.