I'm new to pi-hole (installed this week on my synology) and I was experiencing the same issue as the original poster. Browsing on my pc's in my network were lightning fast responses where the DNS requests were handled by pi-hole, but on android devices it would take a very long time for a page to start loading. I suspected a time-out but couldn't find anything when I ran pihole -d except that the log starts with:
::: IP Address Information
::: IPv6 addresses located
::: Pinging default IPv6 gateway: ping: unknown iface
Gateway Responded.
::: Pinging Internet via IPv6: ping: unknown iface
Gateway Responded.
I'm not sure if this is intended behaviour, but I wasn't able to fix this.
Back to the matter at hand, the android devices. I noticed they used IPv6 for queries when being served by pi-hole. So I looked into my fritz.box network settings for IPv6. I had added the IPv6 DNS address for the pi-hole there and checked the checkbox "Also announce DNSv6 server via router advertisement (RFC 5006)" checked.
Unchecking that box solved the issues on my android devices for me.
At first I was worried this meant the android devices wouldn't use pi-hole for DNS requests anymore, but the tail tool for the pihole.log showed me it did.
Happily enjoying fast ad-free browsing on all my devices in network now.
I know it's pretty specific solution for fritz.box devices, but maybe it helps others.