In Seoul, I would recommend the following places:
Seoul (서울):
Gyeong-buk Palace (경복궁): A beautiful palace with a changing of the guard ceremony on the weekend.
In-sa-dong (인사동): A traditional market area - where you can buy traditional things and sample a lot of different kinds of tea.
Nam-dae-mun Market (남대문시장): This market, like Pamela said, has everything you need and everything that you don't. It can be a little overwhelming as it quite busy and spread out. Not sure if it open on Sundays though...
Nam-san Tower (N서울타워): this has the best views of Seoul (better than the 63 building - in my opinion) but try and go there on a clear day. Also, go there just before dusk because you get to see Seoul in the daytime, twilight and nighttime (the night view is beautiful and the daytime view is mind boggling as you can see the sheer size of Seoul - it's HUGE!)
Dong-dae-mun (동대문): this is a huge shopping district with 24 hour shopping available. It is quite large so make sure you set a lot of time aside for this. I agree with Pamela, at night the night market also opens in the old baseball stadium - well worth a visit. (APM is my personal favourite place to shop here).
Myeong-dong (명동): this is a popular destination for tourists as iit has a mix of cheap, mid-priced and high-brand shops available. When you are in this neighbourhood, you HAVE to go to "Myeong-dong Gyo-ja (명동교자) for Kal-guk-su (칼국수) - it is amazing. I go there, like, once every 2-3 weeks. So good.
I-tae-won (이태원): I recommend this place because it has the largest collection of (authentic) international restaurants in the city. It is very popular with the ex-pat residents but I would avoid buying anything in the shops here as they are often over-priced (however, do buy from the people with the stalls on the street).