There's about a 50% chance that when I leave a building and "enter" Skyrim again, that the frame rate is going to drop to slideshow level performance. It seems to be getting worse as I play more. I currently have Lydia as a follower.

Anyone else experiencing this?

Yes. I'm fairly sure it's a memory leak in that VRAM isn't being purged of unused textures. Eventually, textures spill over into system memory which is considerably slower, hence the FPS drop.

If you wait long enough, you should experience a freeze of several seconds followed by the FPS increasing again. That's most likely the garbage collector finally kicking into action and purging unused texture data. Alt-tabbing will also trigger a purging of VRAM.

Actually this doesn't seem to be as much of a problem now as CTDs. I get about one CTD per half hour of real time.