We got back from BC yesterday --- good trip, though the weather was uncooperative. If you're visiting Victoria, we recommend Helm's Inn
wholeheartedly --- it's a five-minute walk from the heart of downtown, but quiet, clean, spacious, and affordable (even in the middle of the summer rush). I would also recommend Pacific Editions
if you like Northwest Coast native art; the proprietor managed to track down an obscure print from the early 1980s for me in less than 10 minutes.
But of course, what you really go to Vancouver Island for is the scenery...