This is a tough one, goblinchief. I'm also constantly trying to convince my SO to manage stress better and get some exercise, and it's an uphill battle.
When I try to spring an exercise idea on him ("Hey, let's go for a walk after dinner"), the answer is almost always no. I have better luck suggesting things in advance ("Will you walk up to the grocery store with me tomorrow morning?" or "Let's walk over to [restaurant] for lunch tomorrow" or "Let's take the Metro downtown this weekend and wander around," etc.). I even convinced him once to take dance lessons -- I had to drag him there every week, but once he committed to the class, he stuck with it. He always admits afterward that he enjoyed the outing and is glad we went, but when someone isn't used to exercising it takes patience to get him/her there. It's hard to be persistent without feeling like a nag (and as you point out, potentially adding to the stress level).
I keep reminding myself that I haven't always appreciated that exercise relieves stress. I had to figure it out for myself, and so does he, and eventually he will.
One other thought: if you can find a more sedentary activity that you both like and can do together, such as playing cards or doing a jigsaw puzzle or something like that, that can be a real stress reliever too. I've had success suggesting things like that, although even that took a while. Some people just get really mired in their job woes, and they don't realize how much it helps to step away and think about something else for a couple hours.
Anyway, good luck, and don't give up!