"Dot matrix" - an array of dots that you can turn on or off. A character lcd is also a 'dot matrix' but you have limited control over the dots - you have 8 programmable characters that you can set up what dots you want on or off and an inbuilt character generator that has the common characters pre-programmed. A graphic lcd allows you to control each dot without restriction. A graphic lcd requires more work on your part to draw whatever you want and this usually means more ram and flash memory is required.

As for 4/8bit bus - most of the character lcds can use either. The performance impact on using either is pretty minimal. Using 4bit mode saves port pins. I haven't seen 4 bit mode on the graphic lcds, but there would be a performance penalty as to rewrite a 128*64 lcd is 1k bytes vs 16*2 character lcd there is only 32 bytes.

There's plenty of example projects using character and graphic lcds on the web - even if they don't use the same cpu as you, the interfacing is all much the same.