Does anyone know of an audio format that is lossless, playable on an iPod and in iTunes, compatible with Windows Media Player, and holds data tags like album, artist, album art, etc?

I'm afraid all that criteria is probably too much to ask of a format. There are open source lossless formats that support tagging and play in Windows Media Player via the installation of a codec. However, due to the fact these formats are open source and not main stream, they are not intended for portable audio devices with limited storage and are not supported by the iPod. The only lossless format that would match most of your criteria in terms of the software and hardware it is capable of playing on is WAV. WAV plays in WMP, iTunes and on iPods, however this format doesn't allow tagging and the file sizes are extremely large.

Then which format supports all of those devices, tagging, but is lossless, providing the highest quality?

There isn't one. The two lossless formats that support both your criteria are AIFF and WAV. However, neither support tagging. There is also Apple Lossless Format, but as you can probably guess, this doesn't support Windows Media Player.