You have to enjoy riding a bicycle if you want to improve. You also have to be willing to hurt, to accept challenges, to fail, and to follow riders who are stronger and far more skilled. You also have to have time to ride because without that, you're going nowhere. Of the lot, excepting the first, the last is probably the most important. Repeat anything enough, even if it's just vacuuming the house, and your performance will improve.
Whichever route you take, just make sure that where you end up is on a correctly fitting bike. Ill-fitting bikes are not only inefficient but bad for the body. Given that we're only issued one body per life, it's better to adjust the bike to fit the body.
Assuming your old bike's size is fine and since you're at the bike shop, you're ready for the next stage: bike preparation. Ask them to dial it in for you. If you go the used bike route, do the same. Have the wheels trued, bearings greased and adjusted, cables checked and replaced when needed, derailleurs adjusted, chain cleaned and lubed and replaced if needed, chain rings and cogs cleaned and replaced if needed, brake pads replaced and adjusted. All that stuff you've possibly neglected. While you're at it, talk to them about gearing.
If you hate climbs because they're always so hard, the problem might be your gearing. Road riding isn't about being macho with a tiny free wheel cluster; it's about giving yourself the tools you need to have fun on your bike. So if the gearing is high (small cogs in back and big rings in front), change it if you know you're going to spend a lot of time in the mountains and especially if you're dreaming of riding in the Alps someday. You can always change the gearing again when you're strong.
Get yourself some good cycling shoes. Running shoes do not make good cycling shoes. Nor do tennis shoes or cross-trainers or basketball or any number of other sports shoes. What you want are cycling shoes, preferably shoes for clipless pedals. Don't panic; getting out of clipless pedals is a snap, no pun intended. You'll learn how faster than you imagine. They're also considerably easier to exit than shoes with cleats and straps, which require bending over and loosening the strap before you exit.
Why do you want to have your feet attached to the pedals? Because your pedaling will be more efficient. Cycling shoes have stiff soles that transfer all of your pedaling energy into the pedals. Running-type shoes have energy absorbing soles to cushion the impact of foot hitting pavement which, on a bike, translates into less power arriving at the rear wheel.
By attaching your feet to the pedals, you're maximizing that energy transfer. Especially when you learn how to spin. Spinning means driving those cranks around at high speeds with a smooth, fluid rotational movement of the feet. You achieve this by pulling up on the pedal on the up-stroke. There's a wee bit of controversy here because there are riders who swear they are physically pulling the pedal up with their foot while others say at best all that is being accomplished is that the leg weight being supported by the opposite pedal is minimized. Either way, one result is less work for the leg pushing the opposite pedal down. The other result is the ability to maintain a smooth, very fast pedaling cadence with minimal or zero surging during the down strokes, which is where either all of the energy is generated or most of it generated, depending on which school of though you follow.
So buy cycling shoes and clipless pedals. Then go out on a quiet, traffic-less road or into some empty parking lot and practice getting in and out of the pedals until you're sick of it. Then do it some more. You want the move, which is really rather easy, to be automatic. This'll be a bit boring but it won't take long and it'll save you ingloriously crashing to the pavement at some stop sign because you forgot about being attached to the pedals.
Next, buy comfortable cycling clothes. If wearing lycra makes you feel like a bulging sack of potatoes, get some baggy cycling shorts. Then when you walk into a bakery or restaurant, you'll look just like a regular person, except for all that clicking coming from your feet of course. If you don't want to look like a blazing billboard, forget the normal bike jerseys. Truth of the matter is that most of the time, good old t-shirts and such work just fine. But you'll want some sort of bike shorts with the padded crotch because they're more comfortable during long rides. Short rides too until you get used to sitting on a saddle.
Okay, a proper foundation has been laid. You're ready to start learning how to improve your riding!