We wanted concrete, but we couldn't be convinced that concrete over a subfloor would age well and resist too much cracking...
Tile was our next choice, but I felt like we'd really lose the look of a simple, smooth surface.
So our current leading choices are Forbo Marmoleum or Armstrong Marmorette. Both are true linoleum products, so we'll need to strip and rewax from time to time. They are sold primarily as commercial products and secondarily as residential.

[url href=http://www.forbo-flooring.com/framework/DesktopDefault.aspx?menu_id=2462old_menu_id=2462ssm=1]forbo[/url]
[url href=http://www.armstrong.com/resflram/na/linoleum/en/us/collection.asp?lineId=355]armstrong[/url]