With the growing dominance of inverter-based resources (IBRs), the synchronous inertia of the interconnected power systems (IPSs) is affected. The increase in IBRs results in a decrease in the system inertia. The decrease in inertia impacts the initial rate of decline of the frequency. Thus, there is a need for faster frequency response requirements to enhance the dynamic performance of the IPS. With the massive penetration of the plug-in hybrid electric vehicles (PHEVs) into expanding smart cities, PHEVs can act as controllable loads which support the inertial response of the system in a rapid manner. This gives a scope to monitor a large amount of EV operational data to ensure reliable operation considering extensive penetration of EVs. This study proposes a stochastic and iterative based optimization for a two-area interconnected power system (IPS) coupled with a hybrid energy storage system (HESS). The HESS uses 10,000 plug-in hybrid electric vehicles (PHEVs) in each area and a superconducting magnetic energy storage (SMES) device to aid load frequency control (LFC). The 10,000 PHEVs would contribute to massive operational data, which needs to be considered while studying the IPS dynamic performance. Here, we investigated two discrete tie lines: HVDC links parallel to the alternating current (AC) tie line and a virtual synchronous power-based (VSP)-HVDC link parallel to the AC tie line. The controller’s optimal parameters are recorded using two meta-heuristic algorithms, that is, particle swarm optimization (PSO) and biogeography-based optimization (BBO) along with simultaneous coordinated tuning of secondary controller and storage units. Results are taken both in the presence and absence of a HESS with two types of tie links. The analysis is performed with typical load changes and sensitivity analysis scenarios for an accurate record of variations in the outcomes. Thus, the proposed BBO-based LFC tracks the supply and demand variations, ensuring precision and accuracy, indicating improved IPS dynamic performance in smart cities.