I started using Xamarin.Contacts from Xamarin.Mobile and am seeing significant slowness on some phones.
My phone which has 501 contacts takes around 4-5 seconds to iterate through all the contacts.
Another phone on my team has 1331 contacts and it takes 969 (not a typo!) seconds to iterate through all the contacts.
Motorola XT897S (an older phone)
SPH-L900 (Galaxy Note 2)
Location on Google drive of sample Xamarin app that I used to test this: