I think the topic is straying from the OP's question about shared hosting.
The first thing to understand is that FCS is completely separate and
independant from your http hosting account. The .swf, no matter where you serve
it from, can connect to any FCS server, anywhere.
FCs has to be installed outside of the http root directory (which is where
your website is served from), so installing it to a single account on a shared
host's server isn't something that you can do.
Next... we have to understand ports. Http traffic, by default, runs on port
80. Therefore, most http servers are configured to listen to post 80 for
incoming requests. Flashcom, if you want to be able to get past firewalls and
proxies, also needs to be able to listen to port 80 (do a search on "tunneling"
to find out why). Since you can't have two applications listening to the same
port on the same IP, you'll want flashcom to be on a separate IP. You host can
have multiple IP's on a single server, so you'd basically be asking them to set
up an IP for you, install FCS, and bind it to the appropriate ports on the
dedicated IP. Most shared hosts won't do this for you.
This leaves you with a couple of options. You can either run your own FCS
server, or buy shared FCS hosting from an outfit like Influxis or MediaTemple.
The upside to running your own server is that you have access to all of the
configuration files... and once you start developing more complex applications
of when you need to gain additional control of access to various applications
you'll find that to be very helpful.
As for a dedicated server, your traffic volume, criticality of your
applications, and the license you buy will dictate what you need in terms of
hardware and bandwidth. For example, I run FCS with 2 personal licenses. Since
my bandwidth cap is 2mbps, I don't have that many concurrent users, I run FCS
on a desktop computer (WinXP Pro/3.4ghz P4/2g ram) on my network and a 15/2
cable connection. If you'll be serving a lot of people at once, or if you'll be
serving lots of high quality video streams, you'll want to arrange for a real
server in a good datacenter.
The machine the FC server is installed on does not need an http server, unless
you want to serve files over http.