I currently have the 150 mbps version and it doesn't work well in my home, I'm not sure if it's the wall thickness, the fact that it's an internal antenna or what but there's dead spots in my house where my wireless tester shows my neighbors wifi is stronger than mine (in my own house!)
Did you try changing channel? There are around 14 channels, and if you switch to a less-crowded one you will get much better reception (if you were using a crowded channel before, anyway).
This article will guide you to find the best channel, then you need to go in the router settings and change wireless channel.
This is the product page with the
user guide in case you need it.
Devices don't need to know what channel the router is on. After it reboots they should connect again without fuss.
All the machines in the house are gigabit. I do stream to an xbox for an HTPC extender, and the xbox is only 100, so that's a chokepoint. But sometimes I get to moving large files around from one machine to another and my wife and I do a lot of lan gaming. I already have a gigabit switch to connect things.
Ah ok. The switch changes things for the better then. If the gigabit switch connects all gigabit devices then, all such devices will talk to each other at gigabit speeds, while when talking to the non-gigabit devices (router and whatever connected through wifi or through the router's ethernet ports, and the Xbox or any device with only 100 ports anyway) they will talk at 100.
Given that I
really doubt you will ever see more than 2-3 MB/s of raw Internet speed having that part of the network capped at 12.5 isn't a major issue. Although might bottleneck the tablets or other wireless devices.
It's best if you use
Cat6 Ethernet cables. Crappy cheap cables can and do bottleneck performance as they allow more interference to get in and support lower transmission frequencies. But take this as general advice, if you are happy with your Ethernet speeds, then you are fine.
Anyway, back to the job at hand:
I would suggest to first try the suggestion above about changing channels, and if your range needs aren't satisfied by that, then you probably need a router with 300N in the name (300 Mbps). In case you were wondering, most 300 have an external antenna, some even more than one. The ones with external antennas are usually better, but the thing that matters most is the power they are putting in the transmissions and the 300N are putting enough power into it for the average 2-floor Italian household (brick walls and/or reinforced concrete). 150N are good in 1-floor apartments or flimsier wooden houses.
And Gigabit Ethernet ports for the sake of it. They don't add much to the price but will be handy for future wireless devices.
As for what router exactly... heh, it's a fast-changing market. As you see even other experts can give very general recommendations.
Still I can give some advice, but you will have to do some homework.

Don't worry, the leg work is done by Google.
With most electronic stuff, there are reviewers testing and telling their view about all known devices,
this is a review of your current router for example. Don't trust too much customer reviews in your favorite shopping site. They usually lack the technical expertise to give a worthwhile opinion, while professional reviewers usually know what they are talking about.
So you need to google a bit about a device with your requirements (say
Gigabit, 300N, b/g/n), then choose one that looks cool and has a good price, google some reviews ("product name + review") and read them. If most say it's good and has the features you need, you can assume it's good and you can proceed to buy it.