I've done 16x16 puzzles in the past and 25x25. I'd say they were harder and more time consuming, but definitely doable. Biggest I've ever seen is a 48x48!
I've done 16 x 16 cell puzzles and would agree with Animator "An 'easy' 4x4 (boxes) sure isn't harder then a 'hard' 3x3 (boxes) puzzle" and "The main difference between a 4x4 and a 3x3 is that you need to pay more attention, as in more numbers to consider etc... "
It does make a refreshing change, from time to time.