Since this is a Normal-type Gym, you should go to the west of Nacrene City and then head south into the outer area of Pinwheel Forest, where you can catch Throh, Sawk, and Timburr. You should also go into Wellspring Cave to the north and catch a Roggenrola if you can. Purrloin is a good backup because of its strength against Bite and Crunch.
Finding the Gym
The Gym is at the back of the Nacrene Museum. You will see a Dragonite skeleton, as well as a meteorite and other objects on display. Hawes, the assistant director of the museum and Lenora's husband, will take you on a brief tour of the museum and will tell you that the gym can be accessed through the door at the back of the museum.
In the Gym, you get a Fresh Water from the guy at the entrance. The first trainer will send out an L17 Patrat. Use your Throh, Sawk, or Timburr.
How to Get through the Gym Puzzle
To reach Lenora, you need to follow a set of clues that are hidden in the books on the bookshelves. The first clue is in the book "Nice to Meet You, Pokémon!" which you can find in the bottom-left bookshelf. The clue asks you which Pokémon you battled first in the gym. The gym is set up such that Patrat has to be the first pokémon that you battled.
Go to the middle bookshelves and look for a book called The Biology of Patrat. This book has the next clue in it, which mentions a pokémon that has a fire inside and blows smoke when it moves. The note says to find a book about that pokémon, but it says that someone is reading that book right now.
The person reading the book is the scientist in the back of the room. You will fight against her L17 Herdier. Again, Throh, Sawk, and Timburr are ideal. When you defeat her, she will step away from the bookshelf. Read the book that is there and you will find the next note. It asks what type of food can be cooked in a pot and tastes delicious.
The answer is in the bottom-right bookshelf. There is a book about Poffins there. In the book is a note saying to go two spaces back, one to the left, two spaces forward, and one to the right. I'm not sure how it's supposed to lead you to the next clue, but the answer is with the school kid who is standing at the shelf just above the one with the Poffins book. She asks if you need to challenge her in order to meet with Lenora, and you should say yes. She has three L15 Lillipups. Once again, Throh, Sawk, and Timburr are your best choice.
Once you defeat her, check the bookshelf that she was standing in front of. You will find a switch below the book there. You automatically press it, and a bookshelf will move out of the way to reveal a staircase.
Go down those stairs and you will find Lenora.
Strategy for Lenora
Lenora has a level 18 Herdier and a level 20 Watchog. Both of her pokémon have the ability Retaliate. This move increases in power if an ally of the pokémon using it fainted on the same turn. This means that once you defeat one of Lenora's pokémon, the other will have the stronger Retaliate move, so watch out for that. Otherwise, Herdier can use Bite and Take Down, and Watchog can inflict sleep and also has the Crunch move. Both pokémon have Leer.
As with the other pokémon in this Gym, Throh, Sawk, and Timburr are your best opponents. You might want to bring your Roggenrola in as well, especially to deal with the Retaliate move.
The Retaliate move is the main thing to watch out for. If you want to spare your fighting-type pokémon from getting the full force of the powered-up Retaliate, then switch to a pokémon that you don't need to use before Lenora sends out her second pokémon. It might faint, but at least you will protect the pokémon who need to stay in the fight.
Once you win, you will receive the Basic Badge. Lenora will also give you the TM for Retaliate.