So I would not miss the Chinggis Khaan Statue complex - it's not precisely in Ulaanbaatar and it's even a bit far away, but it's really worth going to. It's a very high status in metal of Chinggis Khaan riding a horse. You can climb the statue and be on the horse's head. It's probably a good 1/2 of travel to reach and come back from.
In Ulaanbaatar itself you can't miss Gandantegchinlen , which is a huge Buddhist temple. Make sure to by rice / wheat at the small seller and feed the pidgeons. Going before 17:00 will ensure that some monks are working there praying for people that ask for it. The colors are just wonderful to enjoy.
To have a good view on the city you should climb on top of Zaisan - If you do it by day you'll be in a flow of tourists, if you do it by night you'll see a bigger crowd of local people just enjoying the climb. As a good advice you might want to ask you taxi to wait for you if you reach this area by taxi.
Next to Zaisan you'll find the buddha park , which holds a huge golden statue of buddha. and where you can just feel the view with the statue in it.