What is best way to clean up my contact lists that are synced between Android and Gmail?
In your android/contacts select only to show contacts from your google account.
You can easily delete your duplicate contacts from your gmail/google account. There is a button on the left side in google contacts for that purpose only.
after deleting contacts recognised by google as duplicate, you can sync your contacts and all your duplicate contacts be gone.