Ooh, this is kind of weird.
First concern is if it is really so easy to calculate. 20 cards is still a pretty small deck to end with, and now you have to sort through by cost. However, you're going to be sorting all the cards back into their respective piles anyway, so maybe that's just fine. And in an online implementation it's a breeze, of course.
There was some discussion about cards that work at any cost (and had a setup mechanic that randomized the cost of the card). Could this work with Foothills? The higher its own cost, the more VP Foothills is likely to be worth.
The median cost of the cards in your deck will depend a lot on the kingdom. If there is no trashing, the starting Coppers and Estates will just hurt Foothills a lot. But if you can get rid of all those, Foothills may end up worth a lot more. It has interesting synergies with Remodel-family cards, which increase the median cost of cards in your deck (removing a lower one and adding a higher one), but this may be hard to judge during the game (it's best when you remove a card lower than the current median value and gain one that is higher). Cursers and Looters also do a lot more damage to Foothills than usual.
If you can get rid of starting junk, probably you still have a fair amount of $3 cards (Silver, various engine components), but you'll be unlikely to have any $0-$2 cards. And then the rest depends on the board. It would probably be pretty easy to get a high median though. Again, contingent on trashing.