Shinkos are probably the best bang for your buck with these bikes. I ran a pair for a while and they worked fine. They might wear a bit faster than some brands, but the cheaper cost balances it out. I swapped my front for one with a tread pattern similar to what yours has, but a modern equivalent. I'm not a fan. She looks better, but doesn't ride as nice.
Plenty of selection for the front, but the rear is a bit of a goofy size. You still get options, just not as many.