Good question! I like messy ones like this. May I ask for a clarification? When you write, "I'm not interested in the attributes that have all values filled in but have only 2 unique values..." can you elaborate a bit more about what this statement means? It's not clear to me.
I understand that you have many attributes with missing values. I'm assuming you don't have much stomach for imputing the missing values, a common statistical practice. Can you say whether or not this is a supervised vs unsupervised problem? In other words, do one, two or a few of these attributes qualify as "dependent variables" in the supervised, regression sense of the word?
To your point, this could be treated as an information-theoretic exercise but that's not the only approach. The thing that makes this messy are all of the missing values. Analysts invariable choose techniques that are in their theoretical and training "comfort zone." Information theorists trained in Kolmogorov Complexity will lean towards metrics such as entropy or MDL (minimum distance length), both of which are indicators of nonlinear, bivariate strength of association. There are many more: metrics based on reproducing kernel Hilbert spaces like distance correlations (Szekely), mutual information criterions (Reshefs), and so on.
I mention these as options for a couple of reasons: first, the standard multivariate statistical approaches to dimension reduction tend to be quite unforgiving wrt missing data. The default option for many of these techniques is "listwise deletion" which means that those units of observation with missing data get thrown out at the analysis. If you do have dependent variable(s), then the rankings based on the magnitude of the bivariate metrics mentioned above could be a good start towards attribute dimension reduction.
"Interestingness" is an information-theoretic metric developed, to the best of my knowledge, by Usama Fayyad in his 1996 book on data mining Advances in Knowledge Discovery and Data Mining. He had been asked to analyze data from scans of the observable sky done with the Hubble Telescope. First, he partitioned the "universe" into thousands of quadrants, calculated his "interestingness" metric for each quadrant, then ranked this metric from most to least. In the process, entirely new astronomical discoveries were uncovered. It's worth noting that Fayyad was also the first guy, back in the 80s when he was at the JPL, to train a machine to differentiate between a valley and a mountain, this time based on telemetric data from the Galileo space probe of Jupiter. This is "true" data mining at its best.
Since Fayyad's formulation, the metric has seen wider use and extensions. For instance, there's Huebner's 2009 paper DIVERSITY-BASED INTERESTINGNESS MEASURES FOR ASSOCIATION RULE MINING. I've seen other papers.
Even so, if you do have a PhD with deep training in 20th c multivariate statistical techniques, you are likely to choose one of the seemingly innumerable variable selection routines that are out there. One that a preponderance of statisticians like and prefer is Tibshirani's Lasso technique. It relies on L1 norms and has good properties in terms of regularizing the solution (not overfitting).