Honestly, the best kind of hosting is always the one that gives you the most flexibility. However, the right answer also depends on how comfortable you are with server configuration / the command line.
If you don't have any problems setting things up for yourself, slicehost and rackspace cloudservers are both great, low-cost cloud-based hosting solutions (www.slicehost.com and www.rackspacecloud.com). Given that you want Sphinx and ImageMagick, I would think this may be the best route for you to go, as I don't know of many (if any) shared hosting providers that will have Sphinx available for you. I've used both of the suggested providers and have been quite satisfied with them... it's the best of both worlds: VPS (technically that's all they are despite the cloud aspect) and cheap :)
Only drawback, as I mentioned, is that you're responsible for setting everything up (PHP, Apache, MySQL, etc.)... Slicehost has great docs that walk you through doing so, however, so it's not necessarily a terrible thing.