Finally, I got the Steam-version of Civilization 4 to work properly with Cedega in Linux (OpenSUSE 11.2, 64-bit). I had no success with normal Wine-installations, so I decided to buy Cedega. After a lot of hassle and many failed attempts I got it to work. Here is what I did in the end:
1. Install msxml3 (download) in a Cedega folder, use «Civilization IV» gddb-profile (Windows 98-mode!). Do not install any later version msxml!
2. Install Steam into the same folder (but in WinXP-mode).
3. Go go go!
(As of 27th of May 2010 the Cedega engine 2010052 works with Steam. However, you might have an error «Failed to load platform files.» In that case, rename or delete the ClientRegistry.blob file in c_drive/Program Files/Steam-folder. Then Steam will update properly and you’re fine!)