Grid vs Recast Graph

Hey guys,

My Girlfriend asked me to look into making a city builder as its her favourite genre, so I thought I give it a try…
One of the reference games for me is Manor Lords (free placement not grid based). So I started using AStar Pro with Recast Graph which worked fine, however since I am soon looking into building roads, I learned that Recast is not great for setting up Penalties, so I tried using the Grid Graph, my world is currently quite large 1000x1000 and I might need to increase the size when looking at Manor Lords. However the Grid graph runs with 200 FPS when using a size of 100x100, scaling it to 1000x1000 the performance drops to 20 FPS without any Agents walking around.

So my question, considering you have a game world of lets say 3000x3000 in size, up to ~500 Agents walking around, the need to have them use roads where possible (so preferably using a penalty system), what would be the best choice ? Anyone having experience using penalties on Recast, or should i use 30x30 Grid graphs with a scale of 100x100 ? Or rather not use AStar and use the build In Unity Navmesh ?

Would appreciate any advice.