In Vancouver I went to a northwest Indian ("native Canadian"?) restaurant whose name escapes me. I believe it was on Davie Street; your hotel concierge can probably identify it. It was in a basement, and didn't feel "touristy" at all. The food was very unusual (that's a compliment) and delicious (those two sometimes don't go together). Something you won't find anywhere else.
And if you're a jogger (or just a walker), the 6.2 mile seawall around Stanley Park has the most spectacular views of any joggin path I've found. Plus it's pretty much flat!