Great lists.. I'm just gonna add a few that I use that I haven't seen above:

CalcPad: Calculator with paper-printout look.. great for long calculations, and you can go back to edit any of the previous operations. (portrait + landscape mode with ASR)

NoteSpark: Notes w/ web sync.. and you can share & sync notes to other people too. I use this to keep shared notes with my wife. If either of us edits the note, it'll send notification to the other 'subscribers'.

Keymote: shows a customizable keypad on my iphone, and I can set it next to my keyboard for app-specific shortcuts.

Comic Touch: Adds layers of comic word bubbles and other comic effects to pictures

Ebook readers: stanza, kindle, eReader, iSilo, Classics, etc..

Some of the games:

Nintaii: great 3d maze+geometric puzzle based on 2x1 blocks.

The Deep: best handheld 3d pinball engine I've seen yet..

Boxed In: reverse sokoban, with more variations..


Btw, when I browsed thru the apps that I use "most often" as the thread title suggested, I've found many of them to be mobile clients for popular websites. So I guess I shouldn't mention them, although their packaging and presentation makes them so much quicker, more convenient, and one-hand friendly than if I had accessed them thru the browser.