I've owned the RINO 120, Etrex Legend, Etrex Yellow (most basic.. thus yellow), and Etrex Legend C (one model before the removeable media version).
All Etrex's will work with rechargeable, alkaline, and lithium batteries. There is a setting inside the GPS that allows you to change the battery level detection for more accuracy. From what I remember in the Legend C you have a choice of "NIMH or Alk" in the systems setup.
Good batteries? Go for the longest cells you can find. Sanyo has good batteries but if you can't aquire them locally go with Energizer 2500's or Duracell 2650's.
The mA on the packaging often is not accurate as seen in independent testings here. You get what you pay for, for cells often. To my understanding Energizers are rebranded Sanyo batteries. I think I read that up at Steves Digicam site under the Batteries Forum.
If memory is correct the Legend Cx is the same battery run time as the C model but just with a removeable memory card slot.
If you're using the GPS in cold temps go with lithium batteries. If 0C and up go with NIMH because it's cheaper. If you've got the extra fundage getting a cheap battery analyzer would be worth it. For about $50 USD it's considered rather affordable for the features you get on the BC-900 charger compared to some $400 models I've seen. That can be found at BC-900. It'll charge your batteries like a normal charger but it will also slow charge the cells the first few times to break the cells in so the cells know the max charge and lowest drain thus giving you more of a full charge of the cell. The unit also will tell you the true cells capacity so you'll know how close that cell is to the packaging claim. As you can see in the indie testing some cells claim one thing and are quite way off or close to thier claims. I own some Energizer 1850's and they're pretty good evenbeforeI would that site with thier indie testings the cells held out better the most of the other higher cells I hd at the time and also the site shows it as the cells very close to the true claims of that cells capacity.