You should definitely resize your album art. Even though we now have album art scaling in SVN, it's still best to bring the album art size down enough that Rockbox doesn't have to spend much time reducing the size of one piece of art, thereby leaving performance unhindered.
Here's a small rule of thumb I usually follow regarding album art: On my Mac, I'll use an app to scale down my artwork to whatever WPS uses the *largest* art (this means that, for example, my Gigabeat F and S use a WPS that displays 200x200 album art, the biggest of all WPSes on both players). This way, I'll have decent looking art on both the WPS I use, and whatever other WPS is there, along with good performance.
So for the e250, try reducing it to, say, 140x140 (which is a little larger than the default WPS displays (120x120) but will let you have nice looking album art on future WPSes), and take it from there.