For a start, anything reliable and crypto friendly. If the project grows, i can always migrate.
For now, minimal 1 Core, 1GB RAM and 5G NVM.

So far, im having doubts between Ionos and Ultahost.

You can probably get that for free at Amazon AWS for 750 hours a month, with a new account.
Since you are on a thin budget, I recommend buying AWS credits on this forum to get you started. They are typically 50% off.
Example of a seller I recommend and trust:
https://bitcointalk.org/index.php?topic=5352922.0