I went ahead and tested the number of queries on my own using the TwentyTen theme and WordPress 3.0 with multisite activated, here were the results:
Default (/?p=#)
Index: 25
Page: 28
Post: 30
Category: 25
Date and Title (2010/07/29/sample-post/) or Numeric (archives/123)
Index: 24
Page: 30
Post: 29
Category: 25
/%postname%/
Index: 24
Page: 31
Post: 30
Category: 25
/%category%/%postname%/
Index: 24
Page: 30
Post: 33
Category: 25
Based on this, there's not actually that great of a significant increase between the permalink structures. The category-postname structure only results in 4 more queries over all four page types than the default setup, while the postname structure only makes 2 additional queries and the Date & Title method levels off at the same number of queries.