The Story/Game Sweet Spot

I started my first ongoing campaign in something like 10 years a week and a half ago, and we're meeting again tomorrow. After lurking on G+ and OSR blogs, I was kinda ready for charge-in-and-get-ourselves-killed gaming - that's what I've mostly experienced before. I haven't gamed with these players before, though, and most of them haven't gamed for years. Of course, they surprised me completely.

It became clear during our first session that this group plays their characters as if life is precious. They are careful, and none of them are fighter types (A C&C Thief who is more of a spy, a C&C 0-level magic user, and a 0-level Mountebank jacked from the writeup here initially but will be cut to fit), and all are interested in a level of roleplaying I haven't gotten the chance to do in awhile.  It's going to be an investigator/spy/discover the big conspiracy type of game, but a kill-stuff-and-take-it's-stuff type game.

I couldn't be more pleased! However, I realize that I haven't played in a game like this in awhile that I felt came off successfully. When you take frequent combat off the table, you take out what constitutes the 'game' portion for a lot of people. My concern becomes: how to hit the right combination of 'game' and story.

What I mean is, I and my players prefer to play out things like skill use (there aren't really skills per se as it's Castles and Crusades, but I'm talking about situations that would be skill checks in 3.x and 4.x D&D). I like there to be some mathematical randomness of outcome, and don't want my judgement to be the sole arbiter of success or failure. What, then, are some good strategies for incorporating the more 'game' elements, so it doesn't become amateur theater hour?

What are some good situations that can hit that mix of dice and roleplaying that aren't combats? What are the best ways to balance those?

I have some ideas, of course, and am looking at the story-games forums and various DMGs, but I thought I'd throw it out to see what advice people have.