I stayed in a little hotel almost in the middle of the city, 10 mins stroll from St Marks. It only had a dozen rooms if that, the one I was in was lovely, canopied bed, gilded plasterwork the lot. Cost about 50 euro a night including breakfast the summer before last.
I suppose you'd call it a B&B rather than a Hotel since it didn't offer dinner, but there are so many great places to eat in every Italian city I wouldn't want that anyway.
I just pitched up at the booking office in the railway station and they found it for me, if I can find their card I'll post the name of the place.