In addition to Colin's remarks (which are great and apply to both Android and iOS), here is a bit more detail for Android:
* Variety is the key. Your first few test devices should be very different from each other not only in screen size, but also in manufacturer, Android version, and screen density.
* Definitely include a Samsung phone, not only because they sell well (so your customers will likely have them), but also because Samsung tweaks Android in ways that surface bugs we don't see in other manufacturers.
* Unless you have more specific data on your demographic, pay attention to the general adoption statistics. For example, it's still worth testing on 4.4.
* There were significant changes in the WebView from 4.4 to 5.0, so another reason to test on 4.4 would be if you're using a lot of HTML content.
* Nexus devices are the most loved test devices among our engineering team, because they're cleaner (meaning they don't have the add-ons that so many other manufacturers have). Google devices are also the only devices with which to test previews of latest Android versions (which may or may not be important depending on the target audience of your app).
