The NiMH as stated above are much better as rechargeable goes. Regular alkalines will last longer for usage. Radio Shack used to sell the best batteries. The "rechargeable" alkalines can only be recharged a few times and it is not worth the effort. I would go with NiMH and just keep one set charging while the other one is walking with you. I have a portable CD/MP3 player and I understand the frustration with it running down since the motor must be kept going. You might want to try a portable MP3 player that works on a memory card or something so it would have no moving parts.
Good luck.
- Brian (Who lives in a house powered by rechargeable batteries )