Gregory is far more knowledgeable about that part of Italy than I am, but I'll second Brian's recommendation for Vicenza, an easy daytrip from Verona. My one time in Verona, I stayed for a few days in the campground just outside the city center, a 20 minute walk or so, passing over the Adige on the way. It was a fabulous campground, very laid back, but it sounds like you're not looking for the camping experience and October wouldn't be right for it anyway. (Actually, that's a great time of year to go -- you will be past the bestial heat we've been having all summer.) But no doubt you'll visit the Roman Arena, still in use (did Catullus go there?), read some of the graffiti outside the house the tourist board has decided was Juliet Capulet's, and take in the monuments to the Della Scala family, which hosted Dante in exile. But my favorite single site in Verona was the Basilica of San Zeno, worth visiting for
the magnificent doors alone (click on the third image down). Verona is one of the most beautiful cities in Italy, I think. You'll love it.