The whole point of the song is to mock Gangnam poseurs, and some of the humor in the video comes from showing Psy somewhere that turns out to be a rather some ordinary, unglamorous place— a neighborhood playground instead of an elite resort, a public bath instead of the pool at a fancy sports club, the subway instead of an excusive nightclub, etc. It would be pretty ironic if the popularity of the video made them actual landmarks. At the peak of GNS mania, the official tourism agency was even offering Gangnam Style tours. Anyway, five years on, this is what I was able to find:
According to the Korea Herald, the stable where he dances his horse dance is at the Royal Saddle Equestrian Society (로얄새들 승마클럽), located in Ilsan-dong, Goyang-si a little outside Seoul. It is a private club, so I doubt they welcome tourists, but if you know a member, they might be willing to take you as a guest.
The glass skyscraper in the background at 0:31 and at other points is the Trade Tower, part of the World Trade Center Seoul complex. According to Wikipedia, the building he is dancing on is the ASEM Tower; I doubt rooftop access would be allowed, but the Trade Tower is certainly a landmark.
Outdoor dancing, yoga
The outdoor yoga class and some of the other outdoor scenes take place in the Ttukseom section of Hangang Park
The carousel is he riding at 1:21 is located in Children's Grand Park in the Gwangjin district, across the river from Gangnam.
The scene at 1:33 where he is sailing through the flotilla of tourist swan boats is on the Han River below the Cheongdam Bridge, which connects Gangnam and Gwangjin. The swan boats can evidently be rented from Ttukseom.
Parking garage and elevator
According to TheSeoulStop.com, the dance-off in the parking garage and the thrusting dance in the elevator are at Songdo Central Park in Incheon.
Subway station dance
The dance starting around 2:31 takes place at the International Business District Station in Incheon, according to various blogs.
The dance starting around 3:02 takes place in a part of the COEX Mall in Gangnam adjacent to the World Trade Center Seoul complex. Evidently, it was renovated in 2014, so it may no longer be recognizable from the video.
As for the playground, sauna, indoor tennis court, bath, subway car, toilet stall, and other mundane locations, I doubt it will be possible to track down the exact locations at this late date, and some may have been substantially modified since the video was filmed, or may no longer exist.