I'm considering getting a Quince (Cydonia Oblonga) tree for my dad for father's day in zone 4A, and was wondering how long after planting it would start producing fruit.
Two different plants in the same Family produce quince fruits - Chaenomeles japonica (shrub) and Cydonia oblonga (tree). Unfortunately, neither is hardy outdoors in Zone 4a - even if the plant survives, the likelihood of getting usable fruit is vanishingly small - quince fruits need a long period of ripening in warmth on the bush or tree. Further info below
Information here regarding fruiting requirements
If you want to try anyway, buy a larger specimen of Cydonia oblonga, you may even get fruit the first year, but definitely by the second, all other things being equal (it survives, it flowers and the flowers don't get caught in cold, the flowers get pollinated, etc). Chaenomeles are not usually grown for their fruits, they're more an ornamental shrub, but you should start getting fruit (in a year with good weather) within 2-5 years.