Hi,
I don't know what stats I roll for my Paladin and Fighter, but they both miss like every time they try to hit the monsters.
Is this normal, or have I just rolled the stats wrong?

When it comes to stats: The higher, the better. You can manually adjust them.

I just created a fighter and a paladin with minimal stats and even they were able to occasionally hit the kobolds on level 1 and defeat them.

Definitely get high strength for any character that needs to swing a sword.
At a strength of 17 they get +1 to hit. At a strength of 18/51 they get +2.
At 18/100 (18/00) they get +3 to hit.

Their damage goes up too, with +1 at a strength of 16, +2 at 18, +3 at 18/01, +4 at 18/76, +5 at 18/91, and +6 at 18/100 (18/00).

Since the Beholder series can be kinda hard, don't feel bad about manually adjusting stats to their max when creating characters. Having two frontliners with a +3 to hit and +6 extra damage (e.g. having their strength at 18/100) helps an awful lot.

Don't forget, the higher your ability scores, the more random monsters you have to fight. Or at least that is what I heard.

From my experience this doesn't happen. Do you have a source?
Monsters do spawn after a while, save for a few floors, but I've never heard about an increase in spawns when you're playing with high stats.

I may be thinking of Pools of Radiance, or another game. One game compensates high ability scores with tougher fights.

I wish other games would do something like that. I finished the main quest of Icewind Dale using fireball spells, or something similar and felt let down. No challenge.

I always hated rolling for attributes, but at the same time I feel kinda cheesy just modifying them to the max (silly, I know).

Since folks are talking about it I figured I'd mention a nice compromise IMO, which is using the attribs in EOB2's pre-made party as a template for my EOB1 party, since I assume the devs figured it would be more or less equivalent to a good party imported from EOB1.

The EOB2 pre-made party is a Human Pally & Dwarven Fighter/Thief in the front, and the back-row casters are multi-classers (a Half-Elf Cleric/Mage and an Elven Fighter/Mage IIRC) which I didn't go along with, I just went Pally, Fighter-Thief, Cleric, Mage. Their attributes are way better than anything I'd care to spend the time rolling for, but non-meta enough to feel like an organic party of unique characters:

Paladin: 18/80 STR, 9 INT, 16 WIS, 15 DEX, 17 CON, 17 CHA
Fighter/Thief: 18/78 STR, 10 INT, 6 WIS, 17 DEX, 19 CON, 3 CHA
Cleric: 15 STR, 11 INT, 18 WIS, 16 DEX, 16 CON, 13 CHA
Mage: 12 STR, 18 INT, 10 WIS, 19 DEX, 11 CON, 15 CHA

I shuffled some attributes around to account for the fact that INT and CHA do literally nothing. Pally got 15 WIS, 17 DEX and 16 CON because I preferred the extra AC over the one extra HP per level. F/T got 6 INT and 10 WIS (knowing how much misinformation is in the manual, I doubt there's actually any Wisdom-based bonus/malus to spell resistance, but figured I might as well switch them since INT definitely does nothing even for Mages). Left the Cleric's attribs alone and, for the Mage, switched the 15 CHA with the 11 CON for the extra HP.

Not much reason to not just throw 18s everywhere, nor is there much reason for that matter to take an Elf, and a Fighter/Thief instead of just a Fighter. But if one or two folks end up seeing this who, like me, wanted a middle ground between just making a maxed-out party vs. spending hours rolling for stats to feel "legit", I thought this might be a nice happy medium.

To the OP and anyone else who happens to have similar questions, the Clue Book (included with the download) is really helpful, as is the Data Card (not included but easy to google). They cover stuff like STR determining melee accuracy and are definitely worth reading through. Half the stuff in the actual manual, though, is just a flat-out lie that the devs never actually implemented. Took the above party through EOB1, currently in EOB2 and I'm having a blast with em.