I was not able to find a way to do this with just core. The "access user profiles" permission controls this, but there's no page listing users available other than through the Admin menu, which requires additional permissions. This is very easy to do with a small module. I suspect Views might be your only other choice.