I just saw this post… here are a few suggestions that vary considerably in driving distance and trail distance (you didn't say anything about time/distance constraints) but I'm assuming day hiking.
If you want to stay close to Sidney:
Try Gowlland Tod Provincial Park. If you are looking for a short but very nice hike try the McKenzie Bight trail. If you want something longer just pick any trail that runs down the length of the park (all provide pretty nice walking in this park).
http://www.env.gov.bc.ca/bcparks/explore/parkpgs/gowlland_tod/
If you are looking for a beach nearby Sidney, head for Island View Beach.
http://www.crd.bc.ca/parks/islandview/index.htm
If you don't mind a bit of a drive, head for Goldstream Park. For a short but interesting hike, walk up Mount Finlayson and/or walk to the estuary . For a bit longer hike, cross the road and ramble along the Gold Mine Trail (make sure you check out the Railway Trestle).
http://www.env.gov.bc.ca/bcparks/explore/parkpgs/goldstream/goldstream_park_map.pdf
If you don't mind driving for a couple of hours and want something a bit wilder/remote, try East Sooke Park or the Juan de Fuca trail (JDF). The JDF is a thru hike, so either check out the short piece of trail from China Beach to Mystic Beach or walk in and explore Botanical Beach and a section of the trail that leads from that trail-head.
http://www.eastsookepark.com/
http://www.juandefucamarinetrail.com/
Edit to add: Mandatory to bring good rain gear!