You do need to think about the 3.5v, I have ruined more batteries than I would like to admit by taking them below their minimum charge.
If 8.4 volts is enough for your application I would stick with 2S LIPO batteries and get something around 3,600 mah. These have been around for a long time - so are cheap and reliable. The higher capacity batteries up around 5000mah are pushing the technology, are way more expensive and much less reliable, personally I wouldn't touch them.
You could also look at having two batteries - not connected in parallel, but one for the left side and another for the right side (assuming its some type or symmetric vehicle), this will also extend your run time as each battery is only having to do half the work.
To protect your investment in batteries, get yourself a LIPO Alarm or build one into your Arduino using a voltage divider and an analog input, sound a buzzer and stop the vehicle if either batter gets below 3.6v.