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).