You're getting ripped off on O2 or Vodafone. Get an Ay Yildiz Prepaid card, 25 Euros for 12GB and there's an option to top up of you run out. It's an EPlus MVNO, speeds are pretty good on 3G (~8Mbps).
Coverage is pretty bad on anything that isn't D1 or Vodafone. O2 has okay coverage in cities, but anywhere else it's mediocre to bad.
I used it in Recklinghausen, Dortmund, Dusseldorf and Koln, so yeah, within the cities. You're right, on the motorways the speed was sometimes atrocious, less than 1Mbps
E-Plus does not exist anymore, it was bought by o2.