I have been all of those places and more. Jeonju has a cute village you can see in less than a day, Busan is mainly for beaches, Jeju is uniquely lovely if you go to Seogwipo or along the coast, the east coast is nice too. Off of Jeju is another small island Udo, you can take a ferry, rent a motor bike, and camp on the beach. But be respectful to the other people, when I did this a couple foreigners I met there were drunk and loud, it was bad, many could not sleep and were too nice to say anything, they didn't listen to me either.
I would saw go into the mountains all over, the mountain restaurants are so fresh, the air so crisp, it is so lovely. Book an overnight stay. Take the train or drive going east toward the direction of the 2018 olympics.
Definitely go to Tongyeong and Yeosu, very historic and very beautiful. You can see where Lee SunShin and navy trained, you know they shot arrows from far away so they could attack distant ships. It's very cool.
Gyeongju is historical and really interesting too.
Also in Seoul there is a lot to do
Besides the nightlife and shopping in Hongdae, Itaewon, and Gangnam I recommend Jamsil, Yeouido Park, Gwanghwamun, and go out on the metro a bit east to Gapyeong, and west to Oido to see some islands.
Longest fastest train across Korea is only 4-5 hours so anywhere you go can be done in a day. If you fly domestic use Gimpo airport.