More amenity space would be useful too. Busier terminal creates demand for food options, for example. What's there right now is pretty slim.
HIA seems hamstrung by trying to upgrade the terminal piece by piece. I don't remember how it was done with Billy Bishop, but the changes made there across a very limited space were drastic. To do that while trying to serve the same number of passengers is a challenge.
E.g., they might be able to do something like build additions to handle the operational stuff (outbound baggage is a big one) and then reconfigure that into passenger space. I'm not sure how limited they are in terms of footprint though... they did expand it for the departures lounge a while ago.
terminal map
May be easier to build a whole new half-terminal to serve existing demand on the west side (if possible) and then redo the east to allow for growth.
The site of the terminal itself seems a bit awkward now though, given the air-freight operations to the east and west. Someone in the know could probably speak to that, but seems to me more separation between freight and passenger traffic would be ideal.