could not find a word that alliterates nicely with Tuesday ...has the same initial sound combination of consonant and vowel.

Alliteration does not require matching vowel sounds. Not sure whether nice alliteration does.

If you pronounced Tuesday correctly (i.e., carefully) you could alliterate it with, e.g., tamarind.