Ann, recommendation of a Dedicated server is not wrong, but not right as well. I can understand the hosting provider's tactics to lighten up your wallet - no surprise there.
Moodle core developers have one thing in mind, moodle administrator's ability to play with everything on their server, which is only possible with Dedicated, VDS or VPS, But this does not mean moodle cannot be installed on shared hosting, but which shared hosting? this really matters, a standard shared hosting (which you'll find everywhere) should only be used for moodle as absolute start (less than 100 users) or as staging server (Testing for your production server), try getting enterprise class/business class shared hosting, they tend to be slightly expensive but have more allocated resources, see if hostpapa have something to offer like that, rather than jumping straight to dedicated as per their recommendation.