ウィーン在住です。

両替でしたら、シュテファンスドームの側にあるBankhaus Schelhammer & Schatteraが一番手数料が安いです。
銀行独自の両替レートはたいてい4円くらい為替市場のレートより高いですが、その他の手数料は、１０セント未満を切り捨てられるのみです。
他の大手の銀行では、両替レートも高い上に手数料も取られます。

住所
Goldschmiedgasse 3, 1010 Wien 　シュテファンスドームのすぐそばです。

私はいつもここで両替しています。

その他の銀行の手数料が知りたい場合は、下記のURLを参照して下さい（ドイツ語です）

http://wien.arbeiterkammer.at/pictures/d103/Reisezahlungsmittel2009.pdf