If you're flying down from Germany, a low fare destination that will get you to southern Spain is Jerez de la Frontera. This is sherry country. Also olive oil and oranges. But mostly sherry. Anyway, there are lots of little towns along the southern Atlantic coast - Cadiz is the major centre and well worth a visit, but there are others along the way that might be to your liking. I don't especially recall a great beach in Cadiz, but that wasn't the focus of our visit. Not far west from Cadiz is Puerta de Santa Maria, and after that is Rota, which is where we stayed, since we had free accommodation at a friend's place. It's actually a nice little town, with a very pleasant beach, and a little bit of cultural stuff to do in the town. One of the town's native sons went with Columbus in 1492, and there's a museum in his family home on the main square. Right across is the old cathedral, only about 1000 yrs old, no big deal, really. There's also quite a party atmosphere, this being Spain and all, and it's helped (or hindered, depending on your point of view) because the town is also host to a US Naval base. So there are plenty of foreigners around (we also met a good number of Brits) but a lot of the locals don't speak English so you can still get the local experience by avoiding the restaurants and clubs favoured by expats. The beaches around Rota are lovely but pretty packed in summer (we were there in June one year and over Easter March?April? I can't remember...another) and in the spring are still pleasant but can be pretty windy. There were some kiteboarders from the Netherlands there at Easter who told us the area was one of the best for wind at that time of year. Nice for them, a little chilly for us!