MPEG4 .mp4 video files seem to be popular on mobiles. Some of the medium to high-end mobiles on Symbian such as the Nokia N series like the N95, N82 etc. record and play video in MP4, as does the iPhone. I should think Windows Mobile phones do too but I don't know the specs of those.
Regarding players, CorePlayer looks good for Symbian and Windows Mobile. But I guess you'd have to figure out how to embed these into mobile web pages of your site and a similar way that flash does.
Another option might be to consider the open source royalty free patent free theora video format that is part of HTML5 and the video tag.
As this is meant to be a programming Q&A site I feel obliged to mention something about programming: search for helix community and hydrogen audio for discussions about programming video and audio codecs.