The most efficient non-gravitational way of extracting energy from ordinary matter is indeed to convert it into elements in the $^{56}$Fe region. There is a fairly broad plateau of nuclides with binding energies of about $8.7$ MeV per nucleon, so it does not matter very much which of these you actually turn the source matter into. (However, $^{56}$Fe is the optimum, since it has the lowest mass energy per nucleon, and the number of nucleons is conserved. $^{62}$Ni has a lower binding energy per nucleon, but it is less stable, since some of its neutrons may be converted to protons to release additional energy; effectively the binding energy does not count the amount of energy that is tied up in the slightly greater neutron mass. On the other hand, much of the energy in that would be released in the conversion of Ni or Co nuclei to Fe is in the form of neutrinos, which would be extremely hard to capture.)
However, the amount of energy that can be released via fusion still pales in comparison with what can be obtained using a deep gravitational potential. This does not need to be a black hole. A neutron star will do. The release of energy in a core collapse supernova comes from the enormous gravitational potential energy that is unlocked when a $\sim1.4\,M_{\odot}$ white dwarf (with a radius of thousands of km) collapses into a neutron star (with a radius a just a few km). If you already have a neutron star, you can drop matter onto it and capture the radiation it emits as it accelerates toward the neutron star surface. Under optimal conditions, this can actually release a substantial [i.e. ${\cal O}(1)$—of order 1] fraction of a dropped particle's entire mass energy.
Finally, there is also direct matter/antimatter annihilation, which lets you get all the mass energy out of the source material. However, it requires you to have ready sources of both matter and antimatter, which is not necessarily possible on large scales. (You cannot manufacture the antimatter without putting in just as much energy as you intend to obtain from the annihilation reaction.) So this option will not function with a generic hunk of source matter as your potential fuel.