A lot of users here will probably have installed a custom rom. Most people do, although some can't because of legislation and carrier contracts.
If you want a really good android phone experience, the first step is always to buy a phone for the hackability, not for the specs. A new phone may look fast and great in the store or on YouTube, but wait until you've registered it and used it for a few months on stock firmware, and you'll know that you've been conned out of a great experience and a lot of money. So first visit a site like xda-developers, and start doing research. Take your time with it, find out pros and cons, but search for a reasonably priced mid-range phone with a lot of users and a rich offering of both stock-based and custom ROMs. Why such a phone and not a top tier phone? Because mid-range phones have a much larger user base, there are just more mid-range phones out there than high end models, and there is a lot more development being done on mid-range phones. Also get a phone that you own, don't go for a subsidized plan. Buy your phone before getting a SIM. Don't focus on the SoC specs, those are not the most important for most use case scenarios, but go for as much RAM as possible within your budget and hackable phone selection. Buying used is sometimes a valid option, if you can get a really hackable phone with good community ROM support for a low price. Software is everything on phones, an older generation phone with a custom kernel and custom ROM will often easily outperform a new phone with stock kernel and firmware.
Once you have your phone, you can make it faster and safer, but realize that a phone is never very safe because the only computer you can get full control off is the SoC, you can't have control over the modem, which will always, regardless of the brand, be able to take over your phone and enable carriers and manufacturers and whomever they are in cahoots with, to access your data.
The first way to make it faster, and you don't even need root for this above Android 4.0, is to disable bloatware and "constantly phone home" applications. For a list of applications that are safe to disable, check out https://spreadsheets.google.com/spreadsheet/pub?hl=en_US&hl=en_US&key=0Ag43oj7rLQP4dENZcmhGN0ZUa3pHSENVeXlqUm5vV0E&single=true&gid=0&output=html (source: http://androidforums.com/galaxy-s2-international-all-things-root/337090-uninstalling-freezing-bloatware.html, this is an older list for GSII, but it's still very usable, although some apps might have slightly changed). The most important things to disable are most GApps, most Manufacturer apps, and most social network apps.
Do not worry about your phone's functionality when you disable all of those apps! The right way to use an Android phone is with a custom ROM without installing GApps. In that case, you use F-Droid as software source. F-Droid only has open source applications, and the chances of getting malware in your phone are a lot lower than on the PlayStore or the Amazon Store. You can still get most of the apps available on the PlayStore (like games) by sideloading apk's, which is easy to do, but for freemium games (pay to win games), this is not an option, except when the game has a non-PlayStore pay system. In a lot of countries, there is no payment option in the PlayStore, so especially in those countries, there is absolutely no reason to install GApps or use Google services whatsoever. If you don't want to do that because you want to use the Playstore for games, which is the only difference in service between non-GApps and GApps loaded phones, you can always register your phone on a bogus GMail account, that you only use for your phone's functionality and PlayStore access. NEVER EVER register your phone to a GMail account that you actually use for privacy sensitive data, and NEVER EVER use GApps to access such accounts.
GApps and manufacturer bloatware apps are data hogs, they are slow and not very practical. You "real" email is much better off with an application like K9-Mail + APG. Your SMS and direct messaging is much better off with TextSecure, your VOIP is much better off with RedPhone, etc... these are easier to use, have more functionality, leave you in control, and are not immediately harvested by all kinds of corporations. These applications do not "phone home" all the time and do not data spam your connections, your phone will feel snappier and will always do exactly what you want it to do, and you'll use a hell of a lot less energy, so your battery autonomy will increase enormously. These applications are also open source, they are of better coding quality, so they use a lot less RAM, which again will increase the performance of your phone quite a lot, and it will allow more multitasking.
Some manufacturer apps cannot be disabled without rooting the phone. That's another reason why you should take control over your phone and root it. The first reason though is that when you root your phone, YOU decide which apps get root access, and not Google or the manufacturer or carrier or whomever they are in cahoots with. Once you root your phone, you'll have an application called SuperSU by XDA-developer Chainfire, which will allow you to specify which apps do get root access, and which apps don't. The general rule is, that only the apps that you want to have root functionality (network hacker apps, firewall, bash terminal, etc...) for you to use your phone as a powerful computer, get root access, and that everything else just doesn't. Once you have root access and SuperSU configured to always ask for root access, you can configure your firewall. You can do that with a good firewall app, or do that manually in terminal, which is pretty simple because it uses the linux kernel's own stateful firewall, iptables.
If you want even more performance, you could go for a custom ROM with a custom kernel and specific optimizations. On some phones, it's better to go for a stock-based ROM, because it will enable you to keep all functionality. On other phones, custom ROMs that are not stock-based offer all functionality. Custom ROMs, whether stock-based or not, usually run a lot faster than stock ROMs, and offer quite a lot more control and features, including overclocking features, using better governors, and other things that enhance the performance of your phone.