You might keep the regular influx of advancement points, but commit them to improvement areas (not specific improvements) in advance, to get a random choice of accessible improvements at the end of the turn; leftover points could be discounted from later turns as "useful but inapplicable basic research".

For example, over the course of 7 neolithic turns I could assign 4 points to "materials technology" and get either bone carving (5 pts.) in 2 turns followed by basic pottery (23 pts.) in 5 more turns or native gold, silver and copper smeltering (25 pts.) in 7 turns. Meanwhile, 2 points per turn in "religion" could buy divination (4 pts), rudimentary calendar (7 pts) and blood sacrifices (3 pts)in any order.

With carefully designed tech graphs (many open improvements per category, maybe multiple categories for the same improvement, alternative prerequisites to allow progress before researching everything) this approach would be realistically uncertain (rather than setting out to "invent the wheel", prehistoric vehicle engineers could surprise the player with other useful things like plowshares); it would allow for rational decisions (e.g. if I plan war I'd better invest in "weapon technology") but standard improvement sequences or similarities between successive games would be disrupted.

We're using computers with plenty of processing power these days, there's no reason to restrict yourself to pen & paper simplicity. Look at Wikipedia, you don't see lists of technological breakthoughs, you see lists of technologies and scientific advancements as part of an overall gradual increase in understanding.

Art simulates life, form follows function.