We study the structural and electronic properties of beryllium (Be) and magnesium (Mg) clusters for sizes 2-20 using a two-step approach. In the first step, a global search of the stable and low-lying metastable isomer structures is carried out on the basis of first-principles potential energy surfaces at the level of the generalized gradient approximation (GGA) of density functional theory (DFT). In the second step, vertical ionization potentials (VIPs) and energy gaps between the highest occupied molecular orbital (HOMO) and lowest unoccupied molecular orbital (LUMO) are determined using the G(0)W(0) methods for up to the fourth-lowest-energy isomers. Novel globally lowest-energy isomer structures are identified for Be-14, Mg-14, and Mg-16 clusters. The van der Waals interactions are found to have a stronger influence on Mg clusters than on Be clusters. A second-difference analysis for both the binding energies and HOMO-LUMO gaps reveals a close relationship between the structural stability and chemical hardness for both types of clusters.