For a casual tourist, I’d recommend at least two full days just in Venice. You could easily spend weeks there and still have things left to see. Although it’s not a terribly large city (growth limited for obvious reasons), every little alleyway leads you to something new, whether it’s a tiny, picturesque square (“campo” rather than “piazza” in the Venetian dialect–the Piazza di San Marco being the one notable exception), a narrow canal bordered by a range of beautiful Gothic palazzi, or a lovely church containing a superb Giovanni Bellini altarpiece or two. It’s true that parts of it are overly crowded with tourists (in almost every season except the depth of winter), but the highest concentration of bodies is in the area between the Rialto and San Marco. Just a few yards outside of this area–even in the high season–and you can find yourself mentally miles away from all the hubbub. And in the early morning, you’ll have even the Piazza di San Marco virtually to yourself.
The “must-sees” in Venice are easy enough to find–San Marco, the Doge’s Palace, the Accademia museum, the Frari church, and maybe the Zanipolo (Giovanni e Paolo) church. You could see all of these within two days, and still have some time for strolling about.
Other churches worth a visit include San Zaccaria (which really DOES contain the most superb Giovanni Bellini altarpiece in the world!), the Salute, San Giorgio Maggiore (have to take a vaparetto to get to this one), and Santa Maria dei Miracoli. If you dig Tintoretto at all, you’ll have to visit the Scuola Grande di San Rocco (very close to the Frari church). The Guggenheim museum has been mentioned–other museums to consider are the Ca Pesaro (mainly 19th and early 20th-century art) and the Correr (a combination cultural history and art museum). Seeing all of these would add at least another day or two to your stay.
The best neighborhoods for aimless strolling (and few tourists) are Cannaregio (northwestern Venice) and Castello (eastern Venice). You’ll find the small (and ever-dwindling) residential population in these areas, but also a number of interesting sights–e.g., the church of Madonna dell’Orto, the Scuola degli Schiavone, etc. These areas also tend to feature the best restaurants–you’ll want to steer away from the tourist traps around San Marco (a good rule of thumb, in Venice and elsewhere, is that if the menu is announced in 10 different languages, the food will be less than spectacular).
Gondola rides are tourist traps, to be sure, but consider taking one of the traghetto-boats–they’re also gondolas, but only serve as ferries across the Grand Canal (at points far between the big bridges). The ride is short–half a minute at the most–and they’re not intended to be romantic (no cushions or anything, and they’ll pack in a dozen people or so), but it only costs something like 50 cents, and can actually cut down a lot of time that might otherwise be spent walking out of the way to get to the Rialto or the Accademia bridge. Plus, there’s something magical about gliding along the Grand Canal in a gondola, even if only briefly.
An excursion to some of the outlying islands is nice, but if your time is limited, I’d suggest skipping them–the vaporetto ride can take a lot of time (and the taxi boats are prohibitively expensive unless you’re wealthy or have a large group of people to split up the fare). If you do have time, then Murano is easy to get to, and besides the ubiquitous glass shops, features a magnificent church–Santa Maria e San Donato, up in the northeast corner of the islands. Don’t miss the “dragon” bones behind the high altar! Torcello has very little to see, but what it has is very beautiful (a Byzantine cathedral), and there’s something magical about being on this remote island, surrounded by trees and far away from all the people in Venice. The vaporetto ride to Torcello takes quite a while, however.
I haven’t had any encounters with pickpockets, but over the past 13 years (since my first visit to Venice in 1996), I’ve noticed a marked increase in the number of African guys selling counterfeit goods. This seems true for most large Italian towns.
Lastly, I have to disagree with Teacake about Verona (though I agree with him otherwise, esp. about the importance of art!). I just visited it for the first time this summer (so maybe my impression would change on another visit), but, although the crowds packed around the “casa di Giulietta” were ridiculous, I didn’t think they were nearly as bad as in Venice. Plus, I thought the old city was absolutely gorgeous, with its cobble-stoned streets, Romanesque churches, and the sweep of the Adige river embracing the town… and the Alps looming on the horizon… I fell utterly in love with the place, and was kicking myself for having skipped it on previous journeys. And I’m not even a big fan of “Romeo and Juliet”!
I definitely plan to return to Verona, myself. But I will admit that you can see the major sights all within one day (they’re all pretty close to one another). There was something about the atmosphere in Verona, especially in the evening, that I found really enchanting, and worth drinking in slowly–for that alone, I’d recommend staying there overnight. Still, if you have to choose, and time is limited, you should probably make Venice your base, and make Verona a daytrip.
Shagnasty’s right about the old Roman arena in Verona–they do still stage events there, most famously their annual opera season (which runs from June-July, I think). I suspect that would be the time NOT to visit Verona, however, unless you’ve made reservations far in advance, as the reasonably-priced hotels would likely fill up quickly.
I stayed at a B&B in the old town that I would highly recommend–the Arena Bed and Breakfast (http://www.arena-bb.it/en/index.htm). Very reasonable rates and huge rooms, including en-suite bathroom.