Just to chime in about the Marathon Plus, I, like you, used to have punctures all the time. I switched to Marathon Plus after baulking at the price and have never looked back. I've used them now for years in 35-559 and 47-559 ETRTO and done about 50,000km with them on Sydney streets that are full of glass and debris and I've had one puncture, and they last longer than an ordinary tire too. (The puncture happened whilst cornering, when I ran over a screw which flipped up and into the sidewall)
One problem was that they can be VERY hard to get on or off the rim, depending on your rim. Hopefully you won't be doing that too often though. However, I used to swap them out for knobbys for a bit of mountain biking occasionally. I have changed a few tires but never ones as tight as the Marathon Plus. I'd come away with sore hands and blisters after half an hour, until.... I found this video on YouTube
Follow that and you'll be changing the tire in 5 mins like any other tire. Brilliant!I find the Marathon Plus are perfect for commuting, and fast.
This page lists sizes http://www.schwalbetires.com/bike_tires/road_tires/marathon_plus
ETRTO is the most consistent sizing to look at. You'll need 622 ETRTO for a 700c rim. So 32-622 or 37-622 for example.