rust-analyzer was not installed for me automatically, although it seems to be the default lsp-server for Rustic.
I had to go here and manually install it:
https://rust-analyzer.github.io/manual.html#installation
I also needed to change the client before everything finally worked:
(setq rustic-lsp-client 'eglot)
The Readme should be updated to mention these fixes in Installation as well as Troubleshooting. I spent a lot of time scouring the web to find out about these fixes.
Dropping this here in case it helps someone else.