Sorry for not responding - I just realised I hadn't added myself as a watcher to the meta issue.
Petr: Re aligning to a specific time - this will only do anything when cron runs. For multiple sites - you could stagger when cron actually runs, or configure your tasks so in the admin interface so they don't all run at the same time.
Re: parallel cron - yes about once per minute is how often I was thinking this would run. You could do it even more often if you like and the work will be shared.
-1 for highjacking the end of user requests for cron - in a cluster you do not want cron running on the user facing nodes. Also - when a site is least busy (3am) is when you want to do lots of cron stuff.
Hubert - this code does exactly what you described - each task calculates when it should run next and each time cron runs it only runs the tasks that are due. If multiple crons are running - they will not get handed the same tasks due to the locking.
Re: Priority - I think requiring a defined order for cron tasks misses the point of allowing parallel cron. Even with the current system there is the chance e.g. for users signing up between the auth and enrol steps in cron - this is life. They will just have to wait 5 minutes! If cron is running much more often - this is less of an issue.
Re: optional scripts - yes all "optional" scripts should be run by this new system and we should not have lots of different crons for different purposes. The scripts will no longer get blocked by long running crons and do not have to implement their own scheduling. There will be only one cli cron script.