i have a diamond rio 500.
64MB internal memory = ~64 minutes of music
you can add a 32MB card for a total of ~96mins.
it is small, light weight, works with soundjam and itunes via usb.
i got it new for around $130 with rebates and discounts.
in terms of encoding most solid state or disk mp3 players should play all bit rates.
there is one option for you. you could get a portable cd player that playes mp3 cd-r's. this would probably be your best option. they aren't that expensive(~$100-$200), and you can hold ~600 mins of music on one disk. the only caveats are: 1) you need a cd burner, 2) they are usually made by companies i've never heard of (i.e. you aren't going to find one made by sony, panasonic, etc...) 3) some of these say they only work for specific bit rates( i read this a long time ago on one model).
other option: $400+ jukebox, 6GB storage.