I like Firefox, but it is a bit of a memory hog; therefore, it's less than ideal for a lightweight installation.
So what are the other options?
Opera is excellent (but not open source); it would be my choice. It is available as a .deb from opera.com.
Having removed Firefox, it may appear impossible to get the .deb at this stage, but wget will do it for you (assuming you use the correct url - below correct as of 6 Jan 2009):
wget http://www.opera.com/download/get.pl?id=31876&location=51¬hanks=yes&sub=marine
Download to ~/, then install with dpkg, then use apt-get to resolve the dependencies:
sudo dpkg -i opera (press Tab key to complete filename)
sudo apt-get install -f
Kazehakase is also supposed to be good (and lightweight), and is gecko-based (a la Firefox). It is in the Hardy repo.
sudo apt-get install kazehakase
Midori is up-and-coming, and webkit based (a la KDE / OS X). It is also in the Hardy repo.
sudo apt-get install midori
I am sure there are others: pick your own!
Whichever you install first, should become the default browser. If that doesn't work, see the Menu and Panel Launcher customisation guides to add to the Quickstart menu.