Dom Knigi is in the same area–in fact, IIRC, you walked right past it to get to the Church on the Spilled Blood. Lovely bookstore, three or four stories.
Be sure to stop in at a Teremok somewhere–they’re a fast food chain specializing in bliny, which are basically crepes. Plenty of options–one of my regular weekend lunches when I was in SPb was a ham and swiss blini with a banana and chocolate blini for dessert. I’d love to see these come to the States, honestly.
The Yusupov Palace is where Rasputin was killed; I regret not making a point of going there, but I’m a history buff. From what I understand, getting into the basement where the actual murder occurred (well, started, if you believe the stories) is a bit of a thing, but I don’t know for sure.
Ideally, you should make several trips to the Hermitage. It is unbelievably large, and a single visit doesn’t come close to being enough. I had a student card and so was entitled to free admission; on several visits, I always found something new. Also, while you’re there, keep an eye out for the Hermitage cats out in the courtyard. I saw a few–sadly, the line only goes back to WWII, as all of the cats (and dogs, and rats, and…) in the city were eaten during the siege.
If you can, try to see something at the Mariinsky Theatre–specifically the original Mariinsky. If not, at least see the outside–it’s a gorgeous building. If you’re just a culture buff, the Mariinsky Concert Hall, down the street on Dekabristov, is a great performance space; it’s where I fell in love with opera, at a wonderful staging of the Magic Flute.
If you want a bit of a not exactly Russian Russian experience, I recommend the faux-English pub, Dikkens. If you’re male, be sure to use the restroom while you’re there; it has a simply brilliant bit of restroom upholstery, well designed for a nation known to love a good drink or ten. Also nice is a little pub that I can’t remember the name of, near Mayakovskaya station. They had a local brew, Vasiliostrovskoye, which I can remember the name of–do try it if you see it. I preferred the light, but the dark was good as well.
Also in the non-Russian Russian experiences, there’s a very nice Indian restaurant down at the bottom of Nevsky Prospekt that I also forget the name of; recommended, if it’s still there.
Actually, speaking of restaurants generally: There are an absolute ton of amazing little hole in the wall restaurants in SPb. I’m trying to remember where I found them all–maybe in one of the little tourist magazines you can get for free? They’re well worth seeking out. Oh, and assuming you drink, don’t forget to try the glintwine–a hot mulled wine that’s just lovely.
Oh, and while walking on Nevsky, keep an eye open for the WW2 era sign advising comrades which side of the street was most dangerous. As I recall, it’s on the left side of the street as you’re going “up” Nevsky (away from the Neva).
Honestly, I’m a bit jealous. My time in Russia was a mixed experience–I was incredibly nervous and very alone; it was literally my first time being outside of the United States, and Russia is… a bit of a steep learning curve. But I look back on it fondly now, and I long to go back again someday. Enjoy it!