What about geocaching? A friend and her husband love it.
Geocaching is a great way to incorporate a fun activity with walking, hiking and driving. It’s both outside the box and outside, and adds a point of interest to what might be a glorified walk. And depending now where you live, there could be tens of thousands of geocaches to find nearby.
You don’t even really need a GPS anymore; most people’s smartphones can get the job done much of the time nowadays.
ETA: <shakes fist at Helena330 for posting while I was composing>
If neither of you have ever run before, you could do Couch to 5K together.
My parents met at a square dance. I absolutely love it, and yes, what everyone might think of as dancing skill is not a prerequisite.
God, I miss square dancing. I’m sure Asimovian cringed when he saw this post. 
Geocaching! Esp since you’re living somewhere new, it’s a fun way to explore around. Geocaching.com. It’s nerdy, athletic and mentally stimulating.
Eta: damn, double ninja’d
I’m glad I read the thread before I suggesting geocaching.
Seriously, I second another suggestion: tabletop gaming. It’s my principal social activity (I game with a group a couple nights a week) and there are couples who play. You don’t have to worry about expense as it’s essentially free. Other players are generally happy to provide the games and are looking for new players to join in. And locations like libraries and game shops often have gaming nights that are free and open to anyone. (Granted it’s not a physical activity.)
We all cringed, dear.
My suggestion is go bowling! Not that physical, unless you consider getting up occasionally to toss a bowl on some hardwood physical, but it is inexpensive, super fun, and easy to do for most people.
I’ll also recommend running. I’m a fake funner (never done more than a 5k on purpose) mainly because even though running feels good, doing it for more than 30 minutes gets boring. When you run with the boy, though, it’s actually pretty fun and you’ll run farther than you would on your own without even realizing it.
Bicycling, too. I’ll be the happiest woman in the world when I finally have a suitable cycling partner. It’s so much fun, and super easy, and I guess qualifies as physical even though if you have a halfway decent bike, you won’t even break a sweat.
Trampoline parks. Outrageously fun and more physically demanding than you’d think.
Ever thought about doing Tough Mudder or Warrior Dash together?
Similar to geocaching, but predating it by several decades, is the map-reading compass-using walk-or-run competitive-or-not Orienteering. Like geocaching, you try to find “things” in the woods, but Orienteering uses bright orange flags that sometimes aren’t visible until you know exactly where to look. A Google search shows that there are Florida orienteering one-day events that may be close to you, as well as permanent courses.
Or perhaps you’d like the German-style Volks March - a low-key 3K-5K-10K group walk (that in Germany ends at the beer hall). There’s a Volkssport web site that lets you search for events by state.
I suspect she means the other 23 hours and 58 minutes in the day.
Movies are the thing for the wife and me. But I think bowling is a good idea too; at least that’s more physical than movie watching. And of course, there are little weekend trips. Those don’t have to be far away.
Are game cafes appearing in the US? They’re becoming popular in Bangkok. Cafes that have a large selection of board games for customers’ use. Just about anything that is nonelectronic.
There are a few around but the idea hasn’t really taken off in America.
Primitive skills, you and your husband might enjoy slightly different aspects of the hobby but will still be able to practice it at the same locations. It gives you the opportunity to gather materials which involves hiking, a social network of others doing similar things, an outlet for your creative side, and a cerain amount of physical work actually doing the various skills. Lots of history, anthropolgy, geology, You can take it any direction you like and go as deep into it as you like.
Myself I practice primitive archery and make all wood bows and arrows. Very addictive.
Is there anywhere you can go Stand-Up Paddleboarding? I know several people who have gotten hooked on it.
I read most of the thread, but not enough to realize that two people suggested it before I did. :rolleyes:
It’s called Fantastic Race. There is a big one coming up in April which both my kids are going to do with their husbands. Don’t the name of that one, this one is good practice for it.
My first date with my wife was skating, and we went all the time when our kids were learning. I think it helps to be more or less at the same level.
In NJ we did some road rallies, which involve following directions, writing down information on landmarks you pass, and staying on schedule at checkpoints. Haven’t heard any advertised here but I assume people still do them. Focused alone time in the car, plus you get to see places you’d never think to travel to.
Stargazing?
I recently saw a rerun of an episode of “The West Wing” where an attractive female NASA official took Josh out to someplace away from city lights, set up her telescope, punched some buttons, and showed Josh Saturn, Orion’s belt, and some other celestial object. You could probably substitute that expensive telescope for a more manual one and some star guides.
This is a great thread, me and my husband are now investigating Ingress (does it work in the UK?) and Geocaching, although we might not start that until Spring!
For my 39th birthday a few weeks ago, when my husband asked what I wanted, I said I wanted him to take a whole day off with me and asked that we go to a climbing gym. We were both incredibly sore afterwards, but it was a BLAST.
We also went out one night for a walking tour of a Christmas light exhibit at the local botanical gardens. Also, if you have a local ice skating rink, that could be fun, too.
Canoeing or kayaking? Not in separate boats, but together. It’s a low impact activity, so, easy on the joints. Can be an upper body workout, if done vigorously. Or else just take it easy and float along.
Just posting to say that the “no progrress without lessons” part is not true. If you hit the ball back and forth enough you will get better. If you practice serving enough you will get better. If you want to play competetively lessons may be a plus but for having fun as a couple and getting good excercise they are completely unnecessary.
Go forth, have fun!