In reply to The Ivanator:
I just got back from a trip there last week, climbing a tad under the grades you're looking at. I don't have much experience of a lot of the areas, but I can give you my thoughts on the places we went.
Sella is definitely worth a day or two (depending how long you're there for). Good selection of grades and no where near as polished as I was expecting.
If you don't mind a bit of an approach walk, Olta has fantastic views and a string of good routes at 5/5+(I'd recommend Christmas Dreams, 5+), and 2 very good looking 6b+s which we didn't have time to try. Apart from the 6b+s, the routes were quite samey, so if you don't fancy 6b+ and you and your partner are quick, you might get bored of them before the day is up. The guidebook has a few routes on the "Pinnacle", though these really weren't the effort of getting to them.
Toix again is worth 1 or 2 days. Plenty of routes to choose from. Lots of short 2-3 pitch multi-pitches too if that's your kind of thing. I would recommend Enérgico (6a+) in Toix Far Oeste, which shares a anchor with a 6b+ (6c/+ imo) next to it which was great fun on a toprope.
Our last crag was Echo Playa. Again, lots of routes at your level, and quite varied, though they seemed to be graded quite harshly compared to the rest, especially towards the left side of the crag, so take care.
As I said, I don't know much about what else there is, and there may be some much nicer places, though I don't think you could go wrong at any of the above. (Olta may get a bit boring if you plan on climbing a lot of routes in a day).
As for trad gear, initially we regretted not bringing any, though by the end we were more than pleased with what did without it. Same with a 60m rope, it really wasn't limiting us, though if you wanted to do any of the long (trad) multi-pitches you'll want doubles.
Overall I thought the grades were a bit harsh compared to where I've climbed before. Went to Sardinia at Easter and was climbing 6b/+ quite comfortably, yet I didn't fancy climbing more than 6a+ in Spain. This may just have been my lack of desire to scare myself on what was meant to be a laid back trip, though my partner agrees they were harsh.
Finally, as someone previously mentioned, there's a Carrefour Planet(!) just outside Benidorm, which we stopped by every day for a baguette on the way to the crags.
Best of luck with the weather!
Chris