The guesthouse where I stayed (the Golden Gobi, IIRC) booked tours that worked out to quite a bit under $100/day, IIRC, including transport and all meals. You stayed in gers. Independently it would likely involve either flying or the 20-hour bus ride to Moron and then a shared van (or hire a car & driver) to Khatgal, which is another 3 hours. It was out of my reach on my trip so I didn't get to do, but it sounds interesting. Lodging choices would likely be very limited and possibly not well marked. Roads can really be more like mud tracks once you get out of UB. But you don't have to worry too much about crowds, and the high season is brief (June-August, if that)

In the time I wasn't at Naadam I explored around UB...was really disappointed the Lenin statue was gone but there's still an over-the-top Russian propaganda monument on top of a hill with views. Also a little-known Stalin genocide museum comparable to Tuol Sleng in Cambodia. I kept hoping for a tour group to get together for the national park and giant Genghis Khan statue, but finally did it with a car and driver hired for the day that I ended up partially sharing with people who were staying for a longer tour. The park has some beautiful scenery.