¿Cómo puedo poner imágenes de la calidad que tiene Spotify?

Recientemente me propuse ponerles imágenes a todas mis canciones únicamente porque quería que se vieran tan bien como lo hacen en Spotifiy cuando lo uso en celular. Después de arduos y tediosos intentos lo que he conseguido no es lo que esperaba. Probé con un programa que se llama Mp3tag y ha funcionado bastante bien, pero me parece que aún se puede mejorar. Tengo una sospecha de que la resolución para las imágenes que estoy usando no es la adecuada, a pesar de que he probado con todas desde 500 x 500 hasta 1000 x 1000. Mi celular es un Moto G 2013 con una resolución de 720 x 1280. Adjunto una imagen, a la izquierda está como se ve en Spotify y a la derecha como se ve con una imagen puesta por mi a una resolución de 800 x 800, siendo la de la izquierda el objetivo a alcanzar. Estoy consciente de que son similares, pero la verdad estaría mucho mas satisfecho con un HD como ese.
Desde ya mil gracias a todos quienes respondan, agradezco su tiempo.