If running out of space in your database is the issue, you have to upgrade. You really should have something that is unlimited. Deleting themes and plug ins won't do anything to free up any tables. The information will still be in them. If you have to start clearing tables via phpadmin, you have gone down the rabbit hole. No one should have to do that just to run WordPress. You could try optimizing your DB tables, but if this is also what your host is saying, you really need to just upgrade.
Apparently, the database space was the problem. Even a slight decimal point improvement in that helped solve the problem. But thanks for the help!
Interesting. First time I've ever seen that specific problem. I also learned something new. Glad you got it figured out.