Clarity
First thing I'd like to clarify Agile is not necessarily better than Waterfall, and waterfall is not necessarily better than agile. Depending on your projects sometimes one methodology just makes more sense than the other.
The Problem
The problem they are dealing with is actually more they don't understand what agile is. Likely they consider themselves "kinda agile" because don't know what agile is, but do one or two things that agile companies do like hold daily scrum meetings.
First Step, Respect
You can't force change on anyone, people will only change if they see it as benefitting them. This is almost always the hardest sell in any change to a company culture. (And what you're proposing is a HUGE culture change, one we both agree is worth making, but I warn you now this will be a VERY slow process.)
Before you can really influence any sort of change in your company you need to earn a certain level of respect by those this would effect. This doesn't mean they have to like you or be your friend, only that they respect if you're taking the time to do this it's with good reason. Until you have this your chances of success are negligible. (you might already have earned this, but it's pretty rare for someone new to a company to have this sort of pull)
Second Sell It!
In this case you're a salesman, you're selling an idea / concept. The key to making sales is making the customer want your product. If they don't really want it, they won't buy it.
So how do you "Sell" Agile. This depends on the individuals and the company culture at large. Each person has their own drives, needs, and desires in regards to how they work. Some people want to receive their working order and just disappear for a week or two before turning it in and repeating this. Others like to vet out every little detail and nuance of a task in advance as a group. Both of these extremes can be very happy under agile, but how you sell them agile will have very different approaches.
The quiet worker
Agile has some social expectations that may not be present in the company as it stands. Daily Scrum meetings for example. Trying to sell the quiet working with this will only make them run kicking and screaming. That's literally the opposite of what they want.
On the other hand they HATE their boss constantly asking is their work done, what's the status on this, scheduling meetings to address that task that's ten steps later because it needs to be adapted due to an issue found at the current step, etc.
The Scrum board handles the lion's share of this! Once the boss is comfortable with the board they'll only bother the quiet developer when needed, and just skip to the board for the other stuff.
Agile also doesn't get into detail on step ten until we're closer to step ten. So instead of planning, replanning, and then further replanning you hopefully only need to plan each thing once.
That will make the quiet worker happy. They can get their work and do it without constant interruptions!
The Collective Worker
For the other extreme their are people who prefer to work in teams and favor pair programming and working in tandem with others over isolation. Agile works for them too! If you describe what you just said to the quiet worker they might like it, or it might completely disinterest them. Not that they'd hate it, just it's not very exciting.
For these people the sprint planning and daily scrum can be big sells! No more running people down to check on things! no more bothering people when you need that second pair of eyes. Collective brainstorming of something particularly troublesome needed? No problem! bring it up in the daily scrum meeting and take it offline right afterwards!
Being able to readily access the necessary people to get your work done is a huge sell to the collective worker.
Many many people
There are literally limitless variations in personalities. Some will be easy to sell on agile, others will be very difficult. You need to figure out what a person likes and dislikes work wise to figure out how to get them on your team. Note, you DO NOT need everyone on board, you just need to have the overall momentum in support of implementing proper agile.
Lead by example
Okay, so you've got a good amount of support now. They people want agile... but where do you start? This is where things get tricky. Very few managers will just go off and change their processes, but here's a fun fact you do NOT need your manager to change most of your processes, only a select few.
In this case you should start leading by example. You want to get a proper scrum board? set one up for yourself that is publicly visible. Once some of the other pro agile teammates see it they'll want one. This will naturally lead you to consolidate this into a single board. Once most of the team is already on the board you can start to win get management in on it which can help get those you weren't able to win over into using it. (expect resistance as well, try to win them over, but if you can't management can bring them in line once they're sold on the idea, hopefully though you can win everyone over, or at the minimum get them to reluctantly tolerate it)
Once you've got that board in place you move on to the next process, overtime you slowly convert to being closer and closer to true agile. As you convince management they want what you're selling you can start selling them on breaking things down into more manageable pieces and walla! you're agile!
Cautionary Note
As stated before. Agile isn't necessarily right for everyone / everything. In some cases resistance to true agile will be unmovable. Perhaps the CEO likes planning everything from A to Z and has no interest in breaking it down. In such a case the switch to agile is likely doomed from the start. (At best grim)
If there is a clear resistance to agile practices you need to be careful to not get yourself branded as uncooperative, a trouble maker, etc. Sometimes being the person who swims against the flow to create change is the best thing that can happen to a company. Other times it's a fast track to a pink slip. Make sure people overall want this change and aren't having it forced on them. One is a good thing, the other is going to be messy at best.
Good luck. I've converted three departments I've working in to agile/scrum. It's a long road, and there is no guarantee of success, but it can be worth it.