Yeah, I'd say go for 4 way, then add 8 way later on if you're not swamped with regular bug fixing and balancing type work (Logokas, it's actually more than 2x the work, because up and down can't just be mirrored).
Or maybe only do walks/idles in 8 directions, and snap to an angle for attacks...