Just sounds like a crappy web host. I've always found that a web company that boasts about their unlimited or over the top hosting (IE.. saying they give you 500 GB's space and 1 TB bandwidth.. or w/e) is complete BS. That's like saying they are giving you 1 hard drive on one of their servers. Which is probably BS, because I think most server farms only use 150 GB hard drives because the 300's cost so much.
What they aren't telling you is that you are most likely sharing your own space with other "shared" web hostee's.
Don't trust the "big talkers".
So, to answer your question: 500 visits a day isn't too much, and a shared package
should be able to handle it. If they cannot support you, get a different host.
If you
really want to go the route of getting a dedicated, go virtual dedicated. It's cheaper, and you can see if you need it. Judging from what you shared with us, I don't think you're site is ready to go dedicated.
My flash gaming site gets over 3k unique hits a day, and is on my shared package.
My web host company (link in sig

) limits 25 users per server, and you get what you pay for.