OK, great, you certainly wont regret it!
It is up to you to decide then whether you will stay overnight in Plovdiv or Sofia...as you can see in the blog I have just spent the evening in Plovdiv which was really great.
Plovdiv station: When you exit the station, head left and you will get to a small side building where you will find the left luggage office. They are open all day, at some hours you have to ring a bell to get in, just wait a few minutes and they will open. A piece of luggage was 2 BGN I think. Check out the last photo here rail.cc/en/plovdiv/hauptbahnhof-plovdiv/l249
Behind me you will find the luggage office.
To get to the city, head half-right from the station through the park and follow ulica Ivan Vazov, it takes about 15 minutes until you reach the centre by foot. The centre is not too big, I had no problems navigating...as soon as I got there!
Walked down the wrong street from the station at first until I tried again and finally reached the centre...
At the station, timings are shown in both Cyrillic and Latin so you wont have troubles finding the correct platforms.
I will try to post some pics later.
If you decide to stay overnight at Plovdiv and visit Sofia the following day only, there is a left luggage office at Sofia station as well.