I have to recommend Memory Loss(3.99) made by Dinoroar Interactive. Great artwork and gameplay. The replayability is actually really good if you want to try to unlock the secret stuff by getting Master on a certain number of levels. Helps me sharpen my memory and is a lot of fun to play with my friends and competing with each other. The app has been recently released and is available on the App Store. You can also check out the video link.
BIT.TRIP BEAT - One of the most amazing games I have. Game has a pong-esque feel to it, with amazing music. Play this one with the sound on. This game will challenge you.There's a light version, as well as a $0.99 version.
Why on earth are you forgetting Doodle Jump? You can't exactly play it with others, but it's so wonderful... it just feels wrong to exclude the little four-legged creature!