I found a really suitable solution on marktplaats (which I would have never found without Ada's advice). An Udoo Bolt Gear. It's basically a prebuilt configuration (including a quite nice looking metal casing) of the Udoo Bolt V8, a single board computer slightly bigger than the Odroid (12cm * 12cm) but quite a bit faster.
Ada and I had actually looked into these machines, they seemed like the perfect solution, but new they were completely out of our price range, starting at around 500€ without RAM or an internal hard drive. The one on markplaats would have been closer to 7-800€ with an internal 128GB NVMe SSD drive and 16GB Ram preinstalled. The asking price was 250€ but I talked the seller down to 200€. This is great because we can spend the rest of the budget on a really nice storage solution!
I will go to Rotterdam tonight to pick it up.
Only I never made it to Rotterdam. I rented an electric car because it was difficult to get to the seller's place with public transport. But I didn't realize the battery of the small cars are to small for such short distances, so I got stuck around half way, had to charge the car, and turn around. Will try again tomorrow. The seller was kind of annoyed, fingers crossed tomorrow will be better.