I would say get a theme and mod it. I use Nukemods as my source for themes and links to sites with themes. I have icgstation on my site, but I have mod it extensively so that it's not that easy to spot the original look.
This is the advice I could give. Try to give your theme a unique look and feel. Perhaps go with something metallic ... and try to chose a theme that's not that big. I wouldn't use one with animations and too many "bells and whistles" since it would load in a million years.
yea, it is very easy to put a theme on both phpBB and phpNUKE but keep in mind with those free scripts, there are always bugs so security is not the best. I had a very large Nuke site that was taken over by someone who got in, there was nothing I could do. Same with my phpBB, both happened by different people and at different times. Other than that phpNuke is great.