Android Scripting Environment
A fantastic application that gives you a scripting environment, currently for Lua or Python on your phone. This is an early python script written as a poor man's mapping solution. Obtain your coordinates from GPS, construct an url fit for consumption by google maps and open the browser.

SkyMap
A great way to see the night sky. Using GPS and position information from the phone, the objects in the night sky in your field of vision are displayed.

Connectbot
A secure shell client allowing you to get a local shell (connect to localhost) or connect to an ssh server on a pc. Second screenshot shows emacs running in an ssh session.


FBreader
A very good ebook reader.

Nav4all
In the absence of the google maps application, this is an option to use a map with a GPS. Quite comprehensive maps and a wealth of options. On the flip side, this is free only until 01-01-2010, you cannot use offline maps and the interface is a little messy.

AndNav
A truly free mapping system. You have a choice of renderers (including google maps) and you can store the maps offline by 'preloading' them.

And finally, installing the android SDK on the pc is helpful in various ways. I used adb a couple of times to install apk files when for some reason it wouldnt work when browsing from the phone. And also, of course, to get these screenshots.