> For Alt+C, are peoples’ file and directory layouts such a mess that they need to search entire directory trees to find what they’re looking for?

Have you ever joined a new project? Usually they're both messy and you don't know where anything is.

Besides, even now with plenty of familiarity in my current legacy code base I can use fzf to type filenames or directories without typing the full path.

Ctrl+R is great for those repeat commands in your shell history that you want to use right now but don't want to add to your .bashrc, like repeatedly running a script with some arguments. I think the value of searching your history is self evident.