I originally tried a really cheap VPS with spinning drives (and probably over subscribed) and that was a disaster.
My current VPS has 3GB of Ram and about 60GB of hard drive space similar to the 3GB model here:
I've found Racknerd to be an excellent provider with great pricing if you can snag one of these specials.
The only constraint is storage as Mastodon caches images and will fill the drive even with only me on the instance.
Here is a short thread discussing my experience at the time when I migrated from bitcoinhackers to my own instance:
This server was setup as a means to decentralize the Bitcoin social networking community in a small way. I came from bitcoinhackers.org. The administrator there felt that the users should create their own Mastodon instances to keep the community decentralized so I created this instance.