I second the nomination for Swan’s. Although since you’re in the Lower Mainland, you could always check out a Murchie’s there…
I’ve done both ferry routes, and they’re pretty similar. The difference is where do you want to do your driving: through Delta, or along the east coast of Vancouver Island?
Once you’re in Victoria just walk around like all the old people who live there. And check out the castle. But don’t go expecting fireworks, because it is a retirement community 
The Empress High Tea is a touristy ripoff, in this local’s opinion. There are better teas available, for example (assuming you have a car), motor on up Fort Street until it becomes Oak Bay Avenue (now you’re behind the Tweed Curtain), to a little place called the White Heather tearoom (run by actual Scots).
By all means however, take in the Empress’ curry buffet, in the Bengal Lounge. Great ambiance, and excellent food. The Bengal Room is worth a visit for itself.
Another great (and fairly hip) place with excellent food is the Herald Street Caffe (sic), on, well, Herald Street (just one block north of Chinatown’s Fisgard St).
The funky antiquarian bookstore on Fort Street–Well’s–is sadly no more, the two ladies having packed up and moved to Nova Scotia, presumably to see a total eclipse of the sun. Munro’s is still great, though, and Russell’s books is OK; about two doors down from Russell’s (on Fort Street, one block east of Douglas) is a true Victoria institution: The Dutch Bakery. Stop in for a coffee and a Dollar Roll, or a vanilla slice. Trust me.
One of the younger employees at Well’s has opened her own used and antiquarian bookstore: Sorenson Books, corner of Cook and Fort St (about 10 minute’s walk from Douglas St).
The walk up Fort will also take you past many antique stores; two good malls are Recollections (right-hand side, just east of Blanshard) and Vanity Fair (left side, another 2 blocks–but within sight of Sorenson’s Books).
The BC Museum is fantastic, no question, as is Craigdarroch–the Victoria Art Gallery is just around the corner from Craigdarroch.
And, again if you have a car, you could always come visit Fort Rodd Hill & Fisgard Lighthouse National Historic Sites of Canada. We’re about 20 minutes drive west of downtown via the Trans-Canada. Hint: don’t leave this for after 3 p.m., as the “Colwood Crawl” traffic will more than double your travel time.
Swan’s brewery pub is very good (and they actually have neat loft hotel rooms–just don’t book the one directly over the pub!); but a great pub meal can also be found at the top end of Bastion Square, in another reclaimed heritage building: The Irish Times Pub. If you’re lucky, you can grab one of the little “snugs,” where your beer is passed to you through a tiny door in the wall.
As for the travel–the Nanaimo route sucks compared to the scenery through the Gulf Islands. Go Tswassen. I strongly recommend booking reservations on a holiday weekend, however. $17 for the car, but worth it.
Ye Olde Englysshe Bummpe, with request for followup–how was the visit? Was that you running past my apartment in the Royal Victoria Marathon Saturday morning?
Ah, no, did not do the marathon, although I was oh-so-tempted. No, wait. . . what’s that other word. . . something about “a million years.” Did take the Tsawassen route there, with reservations, but decided to come back via Nanaimo without reservations and that was a mistake (no reservations-- the drive was pleasant enough). The best years of our lives we spent in ferry terminals. . .
We did Craigdarroch and did a little shopping and looked around the Empress and ate at Pagliacci’s which was very pleasant and satisfying for all-- good call. The weather was great and we saw government buildings and boats and all that and drove around the edge where I managed to navigate us back into town on distant memories and was able to show my MIL the fabulous bunnies of U Vic, which made the trip complete. Got back to Van in time to discover that Ginger and Chili was closed and my Thanksgiving ginger beef fantasies werre quashed, but Provence came to the rescue.
Thanks everyone!