How much height do you have in the basement? There are engineered panels that can be put down that allow the floor to breath, and you can then put any surface on them you wish, but they take up maybe 2" or so (depends on brand). If you decide on tile, you'd have to scarcify the floor to remove the paint. Messy, but quick with the right rental tool ( a big surface grinder). To give the floor a chance to breath, Ditra from www.schluter.com would help, as it has channels that would allow water vapor a place to go. If you want to investigate tile more, check out www.johnbridge.com. If the floor gets damp, carpeting directly on it is not a good idea.
The engineered panels would give you the warmest floor unless you used heating mats under the tile.