I'm biased, but I would start with a fuzzer. Fuzzers have two key differences for your scenario that makes me lean towards them:
They provide the will to act. You mentioned the codebase is old and rotting, so a normal bug may not rise to enough attention to fix. Finding security bugs may give greater justification to undertake an effort to start maintaining it properly.
1 fuzzer exercises more than 1 test. I think you'll get more bang for your buck by integrating a fuzzer, whether it is libFuzzer, AFL, Radamsa, or anything else. Fuzzers are not targeted to a single unit and will, ideally, find bugs all over the place from a single, simple starting point.
That said, there are good arguments for diving into the codebase and writing tests too. In fact, writing tests may make your fuzzer more effective.
You only asked fuzzer vs tests, but I'd offer that you should update your build settings before fuzzing. New compilers have a lot more diagnostics than they used to. But then I'd set up libFuzzer or AFL.
> Is fuzzing something for me to improve code quality,
Is it C/C++ and does it include parsers? Then definitely yes. If not it depends.
> or are tests the lower hanging fruit?
Again: Is it C/C++? Then familiarize yourself with the sanitizer features of gcc and clang, primarily address sanitizer. Lots of "rotting" code shows memory safety errors just by running them with asan.