Android does have an API to do that, and as far as I know it's always had this ability. The problem is that developers aren't interested in using it. The stock contact picker can mess with an app's "flow" and it might not match the overall design of the app. Developers would rather implement their own contact picker than use the one the OS provides, and that requires permission to read all contact data.
1) The Android UI designers need to get on it and figure out how to make the contact picker more acceptable to developers. This could involve adding some flags that adjust the look and feel. But keep in mind that Android apps are all supposed to be following common design guidelines anyway, so apps shouldn't be excessively customizing common elements.
2) Don't let apps request access to all contacts in the first place. Don't give them any choice except to use the picker. Obviously it's far too late for this now, but if it had been done this way in the beginning, then there would actually be pressure to make the system picker work acceptably.
