If you're serious about being adventurous, get a decent map and set off across the steppe. Zavkhan is in my opinion the most beautiful aimag (province) of Mongolia, from Khovd just set off east and follow tracks heading in your direction, and ask at gers. I don't know what bitumen you're refering to, but rest assured there is very little of it in the west.
The three main routes are northern: through Olgi, Ulaangom, Moron, Bulgan, UB; central: Olgi - Tosontsengel - Kharkhorin - UB and southern: Olgi - Khovd - Altai - Bayangkhongor - UB. All have their ups and downs, and all are asphalt for the last few 100 kms to UB.
There are really unlimited route-taking possiblities in Mongolia; just string together some places which interest you on a map. Don't expect any great adventure sticking to any of the main routes.
If you really want to try a tough drive, try the road from Bulgan (Bayan Olgi) to Bulgan (Khovd) in the far southwest of the country. The best adventure was just shooting around the Gobi totally off-piste, just using a GPS bearing and working out how to get to places.