In reply to swifty:
It sounds like a very wide grade range, particularly if you both climb at about the same level. If you only climb 6c then 7b's won't be any use to you. And 5a's will probably be too easy to be interesting. I think you could probably comfortably start around 6a and I wouldn't aim to surpass your indoor grade in just one week of climbing. If you're not that familiar with rock (compared to plastic) you'll be best off getting as much mileage as possible - doing lots of routes around 6b with just the odd harder thing if you feel you need more of a challenge.
There are lots of places that fit the bill but another factor to narrow it down is
when you intend going. Some places tend to get hot early. Other places are better later in the season.
In terms of transport if you're going to France you could potentially drive all the way. Anywhere else it's probably best to fly / hire a car. If you don't drive then that will narrow the selection down further still.