In 2002, when cheap travel was a priority to me, I was routed via HKG with CX (courtesy of Trailfinders). Granted, I had to be in HK for a week after SK.

As others have pointed out, Asiana and Korean (they of the Pepsi tailfin logo!) both fly direct, but I believe they're not cheap.

ICN is (or certainly was then, just after it opened) one of the world's greatest airports. And Seoul and Busan aren't bad cities either! Bear in mind if flying domestic, most flights leave from Seoul's Gimpo airport (not ICN).