Has anyone suggested geocaching yet? :D:D:D
Seconded! In Chicago I’d know exactly where to tell you to go, but maybe there are outdoor concerts near you that would lend themselves to that?
How about volunteering for Habitat for Humanity? You can do good work together - and learn to build a house while you’re at it!
Seconding both of these posts. We moved to a new city this summer, and joined a boardgame meetup group, and now we have more friends and a social activity to go to every week! There are so many board games available now, you should be able to find something that you both enjoy if you have any interest in adult board games at all.
It can get kind of physical, if you tend to jump up and flip the table when you’re losing. 
My husband and I did many years of latin dancing and ballroom dancing together - it wasn’t very expensive, and it was quite fun. A caveat - make sure they ensure equal men and women in the classes. We took a few classes that had far more women than men in it, and I was quite irritated by standing around not doing anything while other women were dancing with the man I brought.
It’s the new Rio by Duran Duran!
The wife and I do half marathons together. We walk them which is rather slow. Look for a half marathon that has a cut off time of over 3.5 hours if you are going to walk them. We do about 3 a year and they are spread out so that we have to “train” almost year round together.
You could also consider cycling. If you really want to be together, get a tandem bike. You might want to rent or borrow a tandem first. I’ve heard that it either brings couples together or splits them apart!
Hey, Spice Weasel!
I know you’re a relatively new transplant to Gainesville. Have you explored the various naturey-type things available in the area? If you haven’t visited Payne’s Prairie yet, you’ve got to get out there to ogle at the gators. The Devil’s Millhopper is also really cool, but that’s a quick visit rather than an all-day event. The weather’s getting a bit cold for springs and rivers, but keep those both in mind for next summer.
You mentioned enjoying tennis but sucking at it. I think racquetball is a lot easier to get into, and there are courts at all the major public parks in the city.
I’m on the way out the door but I’ll try and think of other stuff and post against later.
Political activism? There are tons of groups struggling to get their issues out there. You could do many of the activities as a couple I would think. The wife and I attend meetings together, we’ve have done road cleanups, handed out information at events, that sort of thing.
I was going to suggest rock climbing, too. Good workout and you get a nice view of your partner’s rear.
Thank you so much for all these great suggestions guys!
I’m guessing with all the recommendations geocaching is sort of mandatory at this point…
Well, the ice rink thing isn’t going to work out well. They have done a temporary ice rink at the downtown plaza in past Decembers, but I haven’t heard they have any plans for it this year.
My husband and I usually go (well okay we sometimes go) to the gym together, but I don’t really like it. 
A couple of times we have gone to an indoor shooting range, but it’s not cheap enoughto do very often.
Johnny’s ideas were good…have you seen the bats fly from the bat house at Lake Alice? Free every night, though once will probably be enough.
Also not the least physical, but there are some joint computer games. Neverwinter is free to play - you’ll need two computers to play together, but if you have two, that can be fun. And in addition to the idea of tabletop games, there are card games.
I have LOTS of friends that bike. Don’t like it myself (my neighborhood is very hilly and so its frustrating to try it if you aren’t in good shape to start with).
They’re in Gainesville? Florida? Near the prison? There’s always volunteering for executioner.
Cycling - take your pick of mountain biking, road cycling or cyclocross.
It’s great fitness, social, a good way to meet other people (along the road and at the cafe at the end of a ride) and a good way to see the world. We’ve got friends who’ve cycled through France alongside the Tour de France, you can do routes throughout the US and also Vietnam is a good cycling destination.
The only expense is the bikes, and you can start low (try eBay or a bike swap site) and see if you enjoy it before investing in something more exxy. Just make sure you get measured at a bike store first so you can get the right frame size.
Coupling?
Be sure it’s the BBC version, not the crappy US version.
First try Yoga…
Then move on to Acro Yoga! AcroYoga - YouTube
It’s my dream at least to do it with a partner. Yoga can be very inexpensive if you do it on your own though I’d recommend at least a few classes to get a sense of proper alignment and feel.
Check out meetup.com. I signed up for an educational hike (free), djembe lessons (reasonable rates), dinner at a restaurant I never would have tried on my own, and there is a game group that meets at various assorted coffee houses and pubs.
You could give LARPing (live action roleplaying) or SCA/historical reenactment a try. Best case scenario, you have fun, meet new friends, and get into related hobbies (period music, making costumes and props, acting, storytelling, fighting, etc). Worst case, you trie something new and have a story to tell.
Tai Chi is usually inexpensive and way more of a workout than slo-mo for 20 minutes has any right to be. Link for the Gainesville tai chi center.
Are pub quizzes an option in your area? I hear those are catching on in the US now.