I would like to suggest that there is a 128x64 pixel LCD. Its name is LCD 12864 full graphic Smart Controller. It is very cheap and could give a very interesting view of the project.
Please bear in mind, if you can implement the new "LCD" in the code for "Arduino DUE" would be a good advance.
You can also find the separate LCD
And its size is only slightly larger than the 16x2 LCD
No image is mine, just google examples
Thanks and best regards