Camoing reservations? Yes. Especially for the high July-August season.
For BC Parks (Provincal Parks, that are run by private contractors): http://www.discovercamping.ca/
For National Parks (run by the fine people at Parks Canada:
http://www.pccamping.ca/parkscanada/ (the only National Parks around here that you would camp at would be Pacific Rim National Park Reserve (Long Beach/Broken Islands) http://www.pc.gc.ca/pn-np/bc/pacificrim/index_E.asp
or at the new Gulf Islands NPR): http://www.pc.gc.ca/pn-np/bc/gulf/index_E.asp
Pac Rim is astonishingly beautiful, about a five-hour drive north on Vancouver Island from Victoria. Miles of silver sand beaches on the open Pacific, backed by Coastal Rain Forest.
The Gulf Islands are a spotted patchwork of little islands, most half-filled with insanely expensive homes; gorgeous sub-mediterranean type climate scenery. Best seen with kayaks, but there are some larger ones that you can rent a car and drive to, with Bed and Breakfast places (Saltspring, for example).
The Royal BC Museum in Victoria is really very good (and has a Titanic exhibit on at the moment): http://www.royalbcmuseum.bc.ca/MainSite/default.aspx
There’s no shortage of whale-watching tours to choose from. “Prince of Whales” seems to be the biggest, if that means anything.
An excellent (if upscale, medium-expensive place) for a romantic special dinner would be the Deep Cove Chalet: http://www.deepcovechalet.com/ A blowout dinner for two might run $200-$300 with a really good wine, but watching the sunset over the inlet over what is likely one of the best meals of your life…priceless. Had my 21st birthday there (24 years ago, I note with alarm).
A nice lunch spot (considerably less expensive) would be Ottavio, a real Italian bakery/deli/gelateria in Oak Bay village. http://www.ottaviovictoria.com/
You could do a lot worse than getting some nice picnic items from Ottavio and coming out to my workplace, for a romantic lunch at the oldest lighthouse on Canada’s west coast (sorry, no wine allowed, though!) 
: http://www.pc.gc.ca/lhn-nhs/bc/fortroddhill/index_e.asp
Here’s another old “What to do in Victoria?” thread that has some other suggestions: http://boards.straightdope.com/sdmb/showthread.php?t=390803&highlight=Victoria
Enjoy!