Any 3g modem/dongle should work, I'd suggest to get a cheap and commonly used one (which often comes nearly for free with many contracts)
E.g. when I ordered DSL I got a ZTE MF110 for ~10€ including a flatrate for three months one month in advance before my DSL was enabled. See
http://www.3g-modem-wiki.com/page/ZTE+MF110 or
https://wiki.archlinux.org/index.php/ZTE_MF110/MF190 for some details on my model.
Most 3G providers usually offer pretty cheap devices together with such contracts, but often on the contrary those are also quite overpriced, compared to the actual cost of those things.
As an example, the model that M-Net offers, an "XSStick W21 (4G)" seems to be slightly overpriced IMHO. You get the same features as mine, only 3x higher max. download speed with HSDAP+. Question is when you can actually benefit from that.
The Fonic is one at ~30 € which seems OK, although they don't really mention what hardware is provided, and web says they provide different models under the same name.
But you could also simply get some used one much cheaper from eBay or somewhere else. Just for comparison, for 5€ less you'd get a brand new ZTE MF65+ which can do a bit more then just connect your laptop.
Just trying to put that price in perspective.
Regarding providers, either get Vodafone or O2/Telefonica, those offer the best coverage usually.
Although if you know where you want to use that dongle primarily, I'd suggest looking up the 3G coverage within that area for the actual carriers (Vodafone, Telefonica/O2, E-Plus/Base, Telekom/T-Mobile).
For your examples, Fonic and M-Net both use Telefonica/O2 as their carrier from what I saw.