One change I've noticed recently, is that the last few times I ran `M-x list-packages', it didn't display the "new" packages at the top.

Might that be related to the recent changes?

• For the sake of simplicity, when you hit `x' in the package-menu you
  will no longer get two separate prompts for install/delete. You'll be
  prompted a single time for everything.

I think "INSTALL (xxx-y.z) and DELETE (xxx-z.t)" is needlessly verbose. It should probably be "Upgrade (xxx to z.t)", with maybe "and delete the currently installed versions".

I agree.

• Most functions which involve downloading data now take an extra
  optional ASYNC argument (some of them also take an additional CALLBACK
  argument). This defaults to nil. If it is t, any downloads involved are
  performed asynchronously (and, if appropriate, CALLBACK is called
  afterwards).

Shouldn't there be some new tests?

Yes. I'm still trying to figure out how to do async tests. Currently all package.el tests use a local directory as the repository, but the async functions only kick-in for remote repositories.
Should I use GNU Elpa for the tests? Might that cause hydra to unexpectedly complain due to random connection issues?

I have to say that package upgrading being only partially asynchronous looks perplexing. You say yes - it starts downloading stuff in the background - I can move around in the buffer, then suddenly the background process takes over in a synchronous fashion - I can't move cursor anymore and just watch some messages in the echo area. The Compile-Log only pops up at the end.

While parallel downloading sounds good, maybe the overall interface should still be presented in a synchronous fashion.

I agree that's annoying and I have some similar plans. We can change the package-installation logic to first download all files simultaneously, and then unpack/compile all of them in the proper order. So large upgrades would have a significant speed improvement.

• Package downloads are performed in sequence, because it is generally
  not safe to do them in parallel

Why not? Simply downloading in parallel should be safe. Maybe not all at once, but 2-4 at a time, especially if they come from different archives, would be beneficial.

I mis-expressed myself. Package downloads are safe in parallel, what makes it non-trivial is that the subsequent unpacking/compiling needs to be done in the right order (curently a package is installed as soon as its download finishes).