I have purchased a replacement battery just like this for about 10 bucks from Battery Sharks.

I was maybe thinking of switching to another type of battery, that has a higher energy density. What are my options? I'm considering Lipo's but they need a seperate charging and protection circuit.

Li-Ion, I don't know too much about them but know they are safer than Li-Poly. I think their efficiency, sizes, weight etc are pretty much the same as Li-Poly.

Li-Poly are only problematic while charging. If you use a decent balance charger you should have no problems, provided you don't try to charge at more than the rated C value. There is a lot of info on Li-Poly on the internet, ignore the paranoid information about fire etc. use it right and it's perfectly safe. Just be aware of under voltage, you would want a decent low voltage alarm system in place.

A 2S Li-Poly battery is 8.4v when fully charged but throw in a regulator and make it 6v and it'll run perfectly (or run at 8.4v, I do)

Pretty much any battery type will be better than a SLA. It will all come down to funds available.

With very little modification to the battery area you should be able to fit 2 5000mAh 2s Li-Poly batteries in.

Lipo and Lithium ion are just about the same. The difference is how they are built , lithium polymer is like a high performance lithium ion. They use a polymer powdered binder mixed with the lithium paste. When they are charged they get warm. The faster the charge or discharging the more they expand. Because they are packed in layers of foil and plastic they have room to do this which is what gives them their higher current capacity. If you ran the same current through a round packed lithium cell it would expand till it busted the case open and in extreme cases explode and catch on fire. Lipo are really made for that treatment. Most lipo packages not have balance ports to charge each cell to the same voltage for max charge but you can charge them like a normal battery with a regulated charger that charges at the rate that battery is rated for and on a timer so it doesn't overcharge. Those are rules for any battery though.

If you want a higher performance replacement get a 2s lipo battery rated at 2200 ma , hobby king.com has them under 20 dollars and chargers too.

I'm running the KingHobby 7.4V 1000mAH for my smaller robots (Hasbro R2, U-Command Wall-E).

Running a 11.1V 1500mAH I'm using on my Omnibots. It runs fine but I think I will bump up to a higher mAH for a longer run time or double up on (2) 2200mAH.

Cheap and seem to work fine.