Roognation - for more mp3 and lame info than you could ever want, check out Hydrogenaudio (.org, I think). You'll find lots of good stuff on the basic intro boards, as well as links for downloads.
To encode with newer versions of lame, just use the external encoder option, with the path to 'lame.exe' on your machine. (While you're at Hydrogenaudio, you should check out their advice on which compile of lame to use - some are not so good, for whatever reason...)
As for bitrates: most of what I know is from message boards and articles from around the net, and what I have now decided to do, when converting my mp3 collection for use on my handheld, is to use an external lame compression 'preset', which is "--alt-preset 128". Basically this is an encoding mode to give you around 128kbps, at a variable bit rate (VBR). It's specially tailored to give good quality at that bitrate. That gives me more or less 1MB per minute; if you push the bitrate up much more than this, you'll be getting files bigger than you said you wanted...
Just checked that address:
http://www.hydrogenaudio.org