Just showing up in town, without even having made a reservation the night before, is somewhat risky. You run the risk of hitting an area when there's a special event going on and other travelers have snagged everything available. Zagreb is great, but it's the capital and the main business center in Croatia, so there's a lot of demand from folks other than tourists. Although May is well before the peak, I've had trouble finding lodging in coastal towns in several countries, even 2 to 4 days in advance. You'd probably be OK most of the time, but not necessarily all the time. I'd consider the just-show-up technique risky in Istria, etc.
There seem to be a lot of small accommodations (private rooms in people's homes, stand-alone apartments, etc.) in Croatia. They're called "sobe". Booking.com has some such options, but quite a lot are just on the books of a local travel agency. You don't want to use your precious vacation time, wandering from agency to agency, looking for a place to sleep. Unless you're both heavy smokers, you also don't want to end up in a room (however nice) in the home of a chain-smoker, as I did in 2015.
Definitely go to Plitvice Lakes National Park. To assure yourself of a decent experience (as opposed to a mob scene on the walkways), spend the night before your visit very near the park and go in at opening time. That will give you a head start on all the day-trippers and the people who like to sleep late.