Wie bereits gesagt bin ich bei Coinbase unterwegs.
Coinbase finde ich so interessant, da sie nicht nur Exchanger sind sondern mit ihrer Plattform GDAX.com auch eine Trading-Plattform bieten.
Nun meine Vorgehensweise um die Kaufgebühren beim Tausch EUR <-> BTC zu "umgehen"
1. Geld via SEPA Überweisung auf das Coinbase Konto einzahlen (zuletzt hat das nicht mal einen Tag gedauert)
2. Auf die Seite gdax.com gehen und mich mit meinen Coinbase Daten einloggen
3. Auf die Seite für BTC/EUR wechseln und dort dann auf "Deposit" also Einzahlung klicken
4. Dort kann nun Coinbase Transfer ausgewählt werden. Du kannst also Gebührenfrei Geld von Coinbase auf Gdax übertragen.
5. Das eingezahlte Geld wird jetzt über einen Limit Buy Order am Markt platziert, somit wird dir keine Tradinggebühr berechnet (https://www.gdax.com/fees/BTC-EUR)
6. Sobald der Trade durchgeführt wurde hast du deine BTCs auf dem GDAX Konto und kannst dir diese entweder zurück zu Coinbase transferieren oder aber eine Auszahlung auf deine BTC Adresse vornehmen.
Spontan, neben der Liste von @Cystasy fällt mir Lieferando.de ein bei denen du per BTC bezahlen kannst.