How/Where/Can I add more address model validations than just "firstName" and "lastName"...?
You can do either or both of:
Create a plugin with a method that is registered as a listener on this event: https://craftcommerce.com/docs/events-reference#commerce_addresses.onbeforesaveaddress
...and perform validation on the address model before it is saved. use
$event->performAction = false; to stop the address actually being saved if need be.
General notes on how to listen to events and get at parameters is here.
Most likely, the best way will be to use a bit of both front end and back end validation here to make sure you're getting the data you want in the format you want in to your address fields.