Hi thebigmtt, first of all welcome to WebmasterWorld!
3500 visitors per day translates to about one visitor every 25 seconds. If your site is not really heavy on database work, scripting etc, a small server would do. But my experience is that the decision to go for a dedicated or virtual server is not a decision for a period of a few months. What is equally important as your current visitor rate is the amount of visitors you expect in one or two years. Moving a popular site from a small to a large server may give so much headaches, that it may be better to select something a little bit more powerful than you need now.
A good in-between might be a virtual private server. In that case the hosting company installs a virtual server environment on a large physical computer which looks and feels like a single computer, but in reality shares all the resources with other users on that server. Some of the VPS sellers are able to upgrade you to higher plans once your site gets more popular without the need to reinstall anything. You can for example start with a configuration of 256MB RAM and 5GB disk space for a low price, and gradually ask the hosting company to increase RAM and disk space when your site gets more popular. Not all hosting companies can do this with all their plans and Linux based plans are often easier to scale up than Windows based, so you have to make the selection of the hosting company and the server plan upfront.
Just as a reminder, we are not allowed here to give you any recommendations about specific hosting companies.