Improving redundancy and reliability

I run a SaaS service that has been growing fast and we're no longer comfortable with our existing infrastructure.

Currently, we run everything off a single linode. Even just a few months ago there were quiet hours overnight where we could do a server reboot. Now, we can't even install updates without impacting our users.

What I'm still undecided on, is what exactly our infratsurcture design should be.

I suppose the cheapest solution would be to add 1 additional Linode in a different region, and configure a MySQL master/slave relationship? Cheapest isn't the most important thing, but it has SOME importance. I believe this design would require manual failover at the DNS level.

Or, we can use a NodeBalancer with an additional linode within the same region, and again use a Master/Slave configuration?

Or?

I'm a software engineer, and I know my way around linux but I'm no ops genius, so advice is appreciated.