If you choose a host that doesn't allow you the features that you want, then you can always go and get "additional" domain features at http://www.mydomain.com (the better ones are no longer free, but sure saves you having to move host if all you want is the ability to change your own MX or CNAME records).
www.Mydomain.com works well if you want to buy a name from any registrar of choice, and set the DNS to point to MyDomain. Once pointed.. you can through mydomain set up as many sub domain pages as you wish, and redirect each to wherever you wish.
goodluck