Well, possibly a bit of an oversimplification.
Yes, bishops were not usually (or normatively) chosen by the pope until modern times. That would have been impossible. Prior to the development of modern communications it could have been weeks, months or years before Rome became aware of a diocesan vacancy. And, even if the diocese was to be left vacant until Rome did become aware, Rome would not be in a position to know who the credible candidates for the post were, still less to make a judgment between them. And this persisted long after the investiture controversy was ancient history; it’s not until well into the nineteenth century that we reach a point where most Catholic bishops are appointed from Rome. And it’s still not the case that all are.
It’s not quite right, though, to say that bishops “were generally chosen by lay people for the first thousand years or so of Christianity”. For the first thousand years (and considerably longer) lay people - the king, the duke, local burghers, etc - were normally involved in the process by which bishops were chosen. But so were clerics - the clergy of the diocese concerned, particularly the senior clergy, and the bishops of neighbouring dioceses. Precise practices and procedures varied widely from place to place, as did the relative roles, and degree of control or influence of laity and clerics in the process, and whatever the formal position each side had to take account of the sensitivities of the other. And even far-away Rome had some influence - when a metropolitan (archbishop) was appointed, word was sent to Rome (or, occasionally, the new Archbishop went on pilgrimage to Rome) so that Rome could send him the pallium - literally, a particular liturgical vestment but, symbolically, a confirmation of his authority within the church. Rome could (and occasionally did) withhold the pallium, which could severely affect the archbishop’s status and credibility, so there was a strong incentive not to choose an archbishop that Rome would object to.
Unsurprisingly, in general, the closer you were to Rome, the more influential Rome was in the selection of your bishop.
The Pope was chosen by the senior clergy of the diocese of Rome, and by the bishops of the immediately adjacent dioceses. Lay people in the diocese of Rome had no formal role in the process, but were not slow to express views, and the clerical electors were generally sensitive to popular opinion. The Emperor claimed a right of veto - he couldn’t tell the electors who to elect, but he could tell them not to elect a particular candidate to whom he objected.
The investiture controversy was not really about whether bishops would be appointed by the pope or by the king, but whether the process of choosing bishops would be controlled by, and ultimately derive its validity from, the church or the state. At the time, it was never contemplated that popes would appoint all bishops.
In regard to lay people being appointed bishops, Northern Piper points to a Duke of York being appointed Bishop of Osnabruck. This wasn’t an isolated case. Ironically, it is largely because the church won the investiture controversy that such things became practical. It was always the case that both church and civil authorities accepted that a bishop had to be ordained. If the successful candidate had not already been ordained to the episcopacy, then he had to be ordained before he could take up his office. If (which happened more rarely, but did happen) he had not even been ordained a priest, then he had to be ordained as both a priest and a bishop. But the outcome of the investiture controversy was that a bishop owed his spiritual jurisdiction to the church, but his civil status - including the revenues of the diocese - to the civil power. The result was that a layman could be appointed, and could enjoy the diocesan revenues for many years, without being ordained and taking up the spiritual aspects of the office. Some obliging cleric was appointed to deputise for him in the discharge of his spiritual functions until he would be ordained (which, of course, in the case of the Duke of York and many similar cases never happened). If the bishop-elect irrevocably decided not to accept ordination, he was supposed to resign the civil entitlements of his office. But, oddly enough, people in this situation often remained undecided for years, even for decades.