Quick flooring for uneven floor
IMO - It shouldn't be ridiculous to tear up any and all linoleum and tile with a good floor scraper down to the subfloor. Then a nice piece of plywood cut to fit and a bit of paint is a great way to go.

Otherwise, I'd mix up a batch of a Floor Leveling Compound, then a nice piece of linoleum (sometimes had for free as a drop from your local flooring depot).

I'm tend to lean on the "just tear it all out" kind of project, but a leveling compound will not only give you a level floor, it will definitely fill any gaps, crevices, etc.