Hmm... I haven't actually done this, I tended to play adventure games with my sister when I was younger and my wife when I was older, and expect to probably play them with my kids in a few years. However having recently watched a few Let's Plays of my own game and found myself nearly shouting at the screen telling them what to do, it seems like it should be possible if the image quality is decent. You could video chat with the image locked on the game screen and just talk about it as if you were sitting next to each other.
I think the classic style games would work well with this but also you want to make sure you avoid ones where you have to pixel hunt a lot, that would be annoying. I would suggest something like either the Monkey Island games or The Dig (which isn't as funny obviously but has fantastic atmosphere). Or the TellTale Sam & Max games should be good for that. Let me know how it goes if you try it!