The first time of bloatware appearing in mobile phones is not something that happened in 2010s or late 2000s. It was 1999, and it was called WAP. I still have Nokia 7110 and 8310, the first WAP CSD- and GPRS-enabled Nokias respectively, in a perfectly working condition.
WAP was a huge mistake. A separate XML-based markup language (WML) that was "compiled" into some "compressed" binary representation of the same language (WMLC) by carrier-side gateways. And the client side still had to waste the resources for XML-like parsing, and, given the lack of RAM in cellphones at the time, this meant even less content could be displayed on a single page. And the gateway still had to fetch the original WML page via HTTP. A lot of complexity for something that simple.
What should they have done instead? Just adopt Gopher. Yes, it still is alive. Gophermaps are TSV (tab-separated value) files, literally the easiest format for machines to understand with no overhead at all (fields are separated with \t, lines are separated with \r\n). The protocol itself is as straightforward as it can be, much less overhead than HTTP. The client has full freedom of choice of how to display every item type, so WAP-like menus wouldn't be a problem anyway. "Standard" Gopher only has 7-type records for search requests, but I guess some custom types could be invented for form filling, or even Gopher+ format could be implemented. It still would be much smaller mess than what they came up with.
Needless to say, when phones became capable of displaying plain (X)HTML (that happened around 2003), WAP faded away pretty quickly. Because no one wanted to maintain parallel versions of their websites that generally couldn't be generated from a single source because of those WAP limitations anymore. Still, modern MAUI-based phones (MediaTek MT626x and MT6276), Mocor-based phones (Unisoc SC6531x, SC770x, UMS9117(L)) support basic WML pages, and remaining RDA-based phones (Coolsand/RDA CT8851, Unisoc SC6533G) even can run compiled WMLScripts. WAP formats support also remains to some extent in the Opera Mini browser and the devices that run it, but that's another huge flop to be told about another time.