[shaunak]

Audacity: http://audacity.sourceforge.net/
with Lame: http://lame.sourceforge.net/
(Actually only Lame will also do, if you don't mind Command Line)

You could try: 22Khz sampling (Mono) and 48kbps.
The song will sound like its being played over a phone line though.....