As the others say, the options get pretty complicated.
My general recommendation basically echoes Mr Happy's: if you want rechargeables, go AA. This is a pretty safe investment because the NiMH chemistry rechargeables are very stable, and work as drop-in replacements in most electronics, not just flashlights. You can invest in a good charger and start buying batteries first for your flashlights, then anything else you have around that runs on AAs, until the major stuff is covered.
Lithium primaries (non-rechargeables) -- mostly in CR123A form for flashlights -- have high energy density, are lightweight, work better than other battery types in very cold weather, and have great shelf life in storage, usually 10 years. The big catch is that they're difficult to find in retail stores for reasonable prices. If you go this route, you should be prepared to order online in bulk -- you can get prices down to $1.50 per battery or lower this way. There are also
safety concerns to be aware of; when alkalines or NiMHs fail badly, they merely leak, fizzle or melt. When lithiums fail badly, they
explode with highly toxic fumes. (You don't need to be
afraid of lithiums, just
aware and not careless.)
There are various lithium-ion chemistries for rechargeable batteries, but as Mr Happy hinted, in the form factors required for flashlights these are special-purpose batteries that were never intended by their manufacturers to be used by consumers this way. That means there are a ton of complications and safety issues that we have to manage in our heads when trying to use them. I mention this so you know what people mean when they refer to Li-ion, but I recommend just avoiding them for now. Get a flashlight first, see how you use it, then consider coming back for more info on these battery types.
So the main decision you should make is between NiMH AA rechargeables and Lithium CR123A primaries.
Generally speaking, a 2xAA flashlight is able put out as much light for about the same runtime as a 1xCR123A light. 1xAA lights generally top out at a lower brightness, but current LED efficiency is so high that it's often bright enough anyway. 2xCR123A lights can generally go a bit brighter than the others, but most of the gain is usually in runtime. The exact details will vary depending on the lights you look at.
I'll give you an overview of the three main lights I have and why, in case it helps you decide:
The first one I got is a Quark 123²; a major factor in my decision was actually the physical size, which I find fits great in my hand. I decided to just get it, use it, and see how often I actually ended up buying replacement batteries for it. It turns out I'm not going through batteries fast enough to justify going to a special-purpose rechargeable setup, which is great because it means less to keep track of. This is the light I carry when I'm in dark places or expect to need one for work. (I'll add that I rarely use it on Max; I just don't need that amount of light in most situations.)
The second light runs on 1xAA: I already had a rechargeable AA setup for other electronics, so my choice of battery was easy. This is the light I go to when I know I'll want continuous light for a while (since I won't need to
buy batteries), or when other people need to borrow a light. The only situation I've ever run into where this light wasn't bright enough for me was when locating baby quail in the shade of brush -- under full sunlight. Not exactly a common scenario...
The third light is a 1xCR2 (lithium primary smaller than CR123A) on my keychain. My main reason for choosing this one was sheer size and weight, and I use it so lightly that buying replacement batteries is quite acceptable to me. I consider it a backup light in case one of my other lights fails or isn't around, although it sometimes gets used for things like reading schedules, maps, etc.
In hindsight, I would have been happy choosing a 1xAA EDC light from the beginning. (The 1xAA light I have now is not physically designed the way I would want for EDC, a decision I made on purpose because I already had the Quark 123².) Well, mostly happy -- I do like playing with all these different lights and batteries...
Hope that helps a bit.
