Leasing dedicated hardware certainly will give you the best experience performance wise, typically*.
Certain headaches come along with it however, such as managing the machine remotely and not being access the machine due to technical problems outside of your control.
My suggestions would be to check out shared hosting options as a single Terraria server does not require an entire machine to run and in fact one machine can run multiple instances of the server software. Because of this, renting space on a shared machine is far more inexpensive than leasing out the entire machine to yourself.
Also google around a bit for promo codes, many hosts provide them to popular youtubers and prominent netizens as a way to advertise their services to new customers.
Although that being said, for maximum performance and the most control, a dedicated machine to yourself is the way to go. $50 is the minimum to get you in the door.