From an architect's perspective, location is more crucial for companies dealing with tangible items (eg. retail company with different stores where knowing which "location" to receive the goods is very important; or a company with their storage/warehouse a different location than the front store). This is not saying location is not important for companies not dealing with tangible items. (eg. A financial services company could also have offices in different cities and they'd like to assign their employees into different locations)
With that being said, let's take a look at your case. If your HQ is totally moved that no inventory items or employees are still in the old address, you may totally just simply go to setup > company > company information and change your company address (also change your HQ subsidiary's address from setup > company > subsidiaries) and call it a day. Fixed asset wise, just claim the old building as a fixed asset.
However, if you still have employees in the old location and you'd like to track who is where, or certain items that you track inventory that are still in the old location and you'd like to track how many items are in old location and how many have been moved to new location, then adding a new location might be preferable.
In terms of department and class: departments are mostly used just as departments (eg. sales, HR, warehouse, marketing, etc.). Classes are mostly used as product lines/services lines (eg. for an accounting firm, classes can be Audit, Tax, Advisory, etc.; for a retail company classes can Dairy, Fruits & Veggies, Cosmetics, Clothing, etc.) as far as I saw - it's pretty much just a segment that you can use it for anything
I hope that helps 🙂