"Hoje não tem uma feira" is wrong because you are talking about fairs in general, not just one (uma) of them. If you talk in general, you don't need the article. You're not completely wrong, though, you could say that exact same phrase if you're desperate to find a fair and you can't find any. Confront "There's no fair today" with "There is not one fair today!"
"Hoje tem nenhuma feira" is almost right, but you still need the "não". "Hoje não tem nenhuma feira" would be the correct sentence. And no, there's no "double negative equals positive" rule here.
Not always. For example, "nunca" (never) doesn't need "não" before. But in this case "nenhuma" translates to "any" and if you need to express "any" in a negative way you need a "not" before (ex: "There is not any fair today"). Portuguese is the same.
(Notice that "nenhuma" only translates to the negative side of "any". The positive side of "any" is "alguma", as in "Is there any fair today?" - "Tem alguma feira hoje?")
To get all pedantic, I believe in English that "any" is like "zero" in that it makes a plural. "There are not any fairs today" ("There are zero fairs today; "Are there any fairs today – "Is there a fair today...).
Unless it is the strong form, which it is in your last example, "Is there any fair today (I do not care which or where)?"
At least on the left side of the Atlantic.
Because fairs (markets = mercados) used to tell us which day of the week it was. On Sunday there might have been the religious fair (domingo) on Monday the butchers fair (2nd fair), then the household goods (3rd fair), fruits vegetables (4th fair), textiles (5th fair), animals birds (6th fair), and fanciful stuff on Saturday (sábado). Well, actually that is how fair came to mean market at least.
Here is the alternative and more likely explanation rooted in Easter Week/Semana Santa coming from Braga which is considered the religious epicenter and pre-beginning of Portugal:
Feira originally meant rest, hence day of rest and came from the Latin, feria which still means holiday (vacation) in Portuguese.
Though there are indeed a lot of street markets leading up to Easter that week in Braga. :)
Probably the reason why the sentence sounds strange is that any, is a plural form of a/an, so in the weak form (which this is) requires either a plural or uncountable noun to follow. There are not any fairs today, or uncountable example, I do not have any homework today, To most closely match the sentence above would be, Today there is no fair, but to insert any into it would change it to, Today there are not any fairs.
Another form of any can take a singular such as, I will take any suitcase. These strong forms can usually be determined by replacing it with "every" to see if it can still work, or adding, it does not matter what or which.
This is a great website to explore these type of questions: