I'd do as much KE as I could. Was lucky a few years ago to redeem 21-year-old KE miles for an ICN-ULN-ICN RT during Naadam in mid-July! Totally full planes in both directions but I think the other options at the time were Turkish, Aeroflot, Air China and MIAT.

I was coming from BKK via MNL, so I can't speak to the layovers if going from the U.S. I deliberately padded in a 3-day ICN stop on the way over (first time there) and saw the major sites. On the way back I had a long layover and used one of the public baths in Itaewon as both a shower and hotel (they're open 24 hours and a very Asian kind of experience).

U.B. has really grown by leaps and bounds but the country outside it is still only lightly touristed. I wished I could have gone on one of the trips to Lake Khusvogol or the far west or the Gobi, but all were at least 7 days from the backpacker places. So I made do with Naadam and daytrips.