1) The query optimizer doesn't explore all plans, but it also doesn't need to. There are very smart algorithms for exploring branches of microptimizations only when they are likely to improve upon an existing plan, and they range from local search to genetic algorithms to branch-and-cut column generation. Outside of a very limited application of Genetic Algorithms which most users won't ever see used, Postgres doesn't do this very smartly.
2) Most production databases have the same set of queries running on them 99% of the time. Queries are optimized on the spot, or pre-optimized but missing important runtime information. Postgres could take a hybrid approach...pre-optimize queries, but explore LP duality models of the optimization to discover where the thresholds are for alternative plans. For example, use one query plan for all values of columnA, except when columnA = "FOO" or columnB > 42.
3) The statistics that are made available to the optimizer are very rudimentary. Multi-column statistics and conditional probability statistics, for example, are missing. They are left out because gathering such statistics can be very expensive. Understanding cardinality can help understand which statistic improvements could be cheaply obtained, and machine learning models and LP duality information could help determine which of the more expensive sets of statistical information would be valuable for the types of queries that tend to be run on the database. I would estimate that conditional probability collections on multi-column indexes alone could result in massive (order of magnitude) improvements over full table scans.
4) I have not verified this, but I don't think Postgres does any sort of statistical or ML-based analysis on the IO or compute power characteristics of the server. Making this information available could result in huge improvements in query optimization when there is a tradeoff that can be made between IO and Compute (such as how to compress data, where thresholds should be set to activate parallel aggregates and scans, etc.). They could also do some learning on the read-write ratios on a table level, which could also offer some important optimizations.
5) There is room for extensions of the SQL table creation syntax that could make available static information that can both be applied as a constraint but also used for query optimization. For example, lets say you have a multi-column key (or even not a key, but just known in advance) where the information is purely hierarchical from column1->column2->column3. If that is the case, certain values of column3 would only ever occur if column2 = 'bar' and column1 = 'foo'. Even if your query doesn't ever touch column1, the query optimizer could possibly choose to not evaluate a predicate on column3 until it knows that column2 = 'bar' and column1 = 'foo'. And as a benefit, you could get a crucial DML runtime error if that ever magically changes on you.
Now, I just need to learn some C and find some time to hack on it :)