Though nowt to do with things megalithic, check out Kolossi Castle just outside Limassol. Kolossi was built by Richard the Lion Heart at the beginning of the 13th century and later passed into the hands of the Knights Templar. I don't what it is about the place but it sends tingles up my spine every time I go there. It's very similar to Hedingham Castle in Essex (which fell under siege by John while his brother was in Cyprus).

Limassol museum is also worth a visit. There's a good market in the old part of town and a very good Irish pub close by that's worth checking out :-) Be careful if you intending driving - Cypriot road sense is not good - traditional Cypriot food though is great!

Enjoy :-)