Cardio Trainer - best app for automatically keeping track of running, biking, etc. Very simple and easy to use.
Robo Defense - insanely addictive tower defense game. IMO the best one on Android (although it may just be that I'm getting burnt out on them)
Google Goggles - not exactly super useful, but it's a great toy to show off your phone. You take pictures, it identifies them. It's good at books/CD/DVD covers, barcodes, logos, text (which it can then translate) etc. You can even take a picture of a sudoku game it will solve it for you!
Dolphin web browser - WAY better than the stock browser. It adds tabbed browsing, easier access to your bookmarks, and built-in Flash blocking (works just like Flash block for Firefox - an icon appears where flash content would be, and you have to tap it to unblock that item).