Lots of great suggestions in here, especially numbers 19 & 20. Some high level, tough bosses located throughout the game would be very cool. I personally hate it how the game just ends so abruptly after the defeating the final boss...I felt like I wasn't done with my characters yet.
