Have you tried Primal ? 

 An nprofile could be useful, it includes relays. I've mostly only had issues with some npubs taking awhile to find.

https://github.com/nostr-protocol/nips/blob/master/19.md#examples

Challenge with searching by names is potential for a lot of fake duplicates, and be quite confusing. Using a follow graph as a web of trust could work, some clients might do this for searching for npubs to mention.

For a name instead of an npub or nprofile, domain names that redirect to a nostr nprofile (with a fallback) can also work well. I've tried 307 redirects and it works, however an HTML page has the option to display something if there isn't a native client available. Could be also a good use of njump. 

 This, nprofiles helps for a robust discoverability; nip-05 (that can contain hints) make things easier with a memorizable and uptadable entry point.

Search by name (or nip-05 substring) can be more effective simply showing first the followed and then ranking by followers count (should be easier to cache that reconstruct a social graph). 

 Yeah, makes sense. It could be possible to keep a cache of the follow graph local for quick usage. Perhaps update it at some interval, or when profiles are loaded. 

 Because it goes against the core idea of nostr - decentralization. In general, currently community consensus is that you have to learn without that feature 

 Yes that happens from a long time, normally when you type @ clients show you cached profiles of start to try to find, but its slow, things can improve a lot, when i have a situation where I wan to tag someone and my client cannot find it, i use nostree.me/search/whatever and y get the npub from there and its just @npub...