You should never get the cheapest motheboard as that would be by Biostar or ECS or other crappy brand.
But there is nothing wrong with an H110 board and skylake cpu (H110 will still likley not ship with updated bios for kabylake so you are rolling dice on risk of it not booting with your cpu and costing you another $50 in either shop fees or cheap cpu to make it work).
Now in regards to your statement an i3 will not hold 60fps on ultra today (at least for any high end titles), let alone the future.
The 580 is on the tipping point of being too much for the i3.
Since you are on a budget here is my suggestion:
Pentium G4560, which is a $60 cpu with 85-90% performance of a i3 7100, + B250 motherboard (agian H110 will likely not have supporting BIOS) + 8GB DDR4 memory. This combo will run around $180 USD. You can then upgrade to i5 latter on down the road.