You are no true Nintendo fan.
"Many of the level ups will net you barely any stat gains, so they are kinda a waste. But every now and then you also get a big level up that compensates for the ridiculously awful gains from before, so it's not as bad as it sounds at first."
There are far worse level up systems. This is a non-issue.
"As for battling foes specifically, it can be a frustrating experience depending on the dungeon. It also doesn't help that the cast of characters isn't particularly well-rounded. Ness is a powerhouse with by far the most HP and a good amount of PSI points. Paula is prone to dying with her low HP and her PSI attacks don't make up for her vulnerability. Jeff has no PP altogether, but he isn't strong either; he is a waste of a character slot. Poo is a piece of... actually, he is second best after Ness; good HP and PP, reasonably strong and can be used in different ways."
Paula's PK Ice heavily makes up for that, try to use Ness's skills in the final battle to see if it works well. PK Fire is no slouch either and she has other cool abilities as well. Jeff's bottle rockets are very useful for certain enemies.
"Where all of the aforementioned hurts is that enemies tend to hit your weaker characters more often. Occasionally you also find yourself in areas where you get bombarded with negative status effects, but the most frustrating thing is that your party has atrocious accuracy with regular attacks. When you have to hope that your characters actually hit the enemy, then there is something wrong. This is poised to lead to nasty situations on a regular basis, because your party repeatedly can't finish off enemies before they use status effects or strong attacks."
That is not true at all. It sometimes happens, but the equiped item is part of the reason. Ness has a couple of weapons that have very high attack but will fail to hit anything. The status effects ups the challenge significantly and are what make the battles rewarding.
Khan: "It does seem a bit like No More Heroes, that is, a game which relies heavily on its distinct style and brimming cleverness to be memorable, but is not mechanically solid."
Don't compare a masterpiece with NMH.