My personal favorites:
Wolfram Alpha (worth the $1.99 for the keyboard alone)
Vector Runner (good for killing a few minutes)
Strategery (like Risk, but named after a Bushism)
Plants vs Zombies (do you really need to know why to get this one?)
Harbor Master (free)
Star Walk (it's essentially a portable planetarium)
PaperDesk (note-taking program that lets you switch between typing notes and sketching notes instantly on the same page)
GoodReader (makes reading pdf files much easier)
Eyewitness (free, beautiful collection of photos that are updated frequently)
Mahjongg Artifact 2 HD (freaking addicting)
X Comics (free, has an amazing collection of comic series, the first issues of which are usually free)
Tap Tap Radiation (free Guitar Hero-esque game, but requires you to pay for any more songs past the 5 free ones)