Mega. With this sort of project, you can run out of memory before you run out of pins anyway, and you are likely to later need more tomorrow for something you haven't thought of yesterday, so you might as well get a Mega to start with. Also, while I'm not so sure a Mega is vital for a larger LCD display these days, it probably broadens your options. You justify the 12v PSU, but you should also consider running Arduino therefrom via decent 5v regulator.