É com satisfação que leio que vais adquirir a bike numa loja física. Sobretudo sendo a tua primeira bike de estrada acho que é uma boa opção fazê-lo.
Mas já agora deixa-me dar-te uma última dica em relação à loja porque o mais certo é chegares lá e afirmarem categoricamente que o teu tamanho é o 56… No meu caso nas lojas sempre me indicaram tamanhos 54 ou 53 como sendo o meu tamanho e não é correcto. O teu objectivo deve passar sempre por experimentar os dois tamanhos. O ideal seria mesmo que te deixassem dar uma volta ainda que curta em ambos os tamanhos da Madone que estás a pensar comprar…
Mas se por qualquer motivo isso não for possível tens sempre a possibilidade experimentar outros modelos na Trek com geometrias parecidas como por exemplo as Domane ou as Serie 1 (modelos 1.x). Sugere isso mesmo se eles se puserem com dificuldades em relação às Madone. Em relação aos tamanhos se forem teimosos (como são na maioria das vezes) e não quiseres ser bruto, dás uma treta que no fim de semana tiveste oportunidade de experimentar um tamanho 54 e 56 de outra marca e ficaste na dúvida. Se te perguntarem marca podes dizer Scott, Specialized ou Cannondade, para os tamanhos 54 e 56, nas várias marcas, as diferenças nos top tube são de mm… Assim deixas o vendedor a pensar que eventualmente houve outra loja que te deixou experimentar e colocas mais pressão no tipo…
Mas se ainda assim não te derem a possibilidade de experimentar, tens duas hipóteses: mandar os gajos passear e ires comprar uma bicicleta a outra loja onde te tratem melhor ou, então se quiseres mesmo muito aquela bicicleta, chegares a um acordo com o gerente (ou dono da loja) em que caso aches que o tamanho não é o adequado possas ir à loja, passado um curto período de tempo, trocar pelo tamanho acima ou abaixo do mesmo modelo, sem custos. No caso deles não deve ser muito dramático porque como disseste tem os 2 tamanhos em stock.
Por último eu não mencionaria de imediato o bikefit, por dois motivos:
1- Assim que falares nisso vão-te disparar os 1001 benefícios do bikefit, etc… e moer-te a cabeça até que aceites. Desta forma, eles não só vão engordar a factura com um bikefit que normalmente custa entre 150-200€, mas também há possibilidade de no bikefit te recomendarem que troques o selim, o tubo de selim, o avanço, etc… e adivinha onde é que tem o material que precisas??? Tudo isto sem que tu tenhas tido oportunidades de meter um kms na bike para perceberes se realmente há algo que te incomode ou não.
2- Acho que um bikefit feito por um bom profissional de forma independente é sempre útil, mais ainda quando o nosso corpo se queixa em cima da bike ou depois de uma volta longa. E no teu caso não vou dizer que seja má ideia… agora o que eu faria, seria dar umas voltas à seria na bike para perceberes como o teu corpo reage à posição na bike, ia fazendo alguns ajuste no selim (tens montes de videos no youtube que te dão boas dicas e podes sempre colocar questões aqui) e se ainda assim achasse que era melhor um bike fit nesse caso avançava. Aí não iria a uma loja, visitaria de forma independente um profissional dessa área (que até pode eventualmente ser um tipo que também trabalhe parcialmente em lojas) mas garantido que o fit que faço com ele não esteja associado a nenhum tipo de parceria com lojas. Pelo sim pelo não, assim garantes recomendações mais imparciais sem outros interesses por trás. O facto de também teres mais experiência em cima da bike também te vai permitir explicar melhor ao bike fitter quais são os teus desconfortos e que tipo de posição queres adoptar (se bem que um bom bike fitter deve recomendar a posição ideal tendo em conta a biomecanica e elasticidade do indivíduo em questão).
Boa sorte e um abraço
Ahh e depende dos sapatos, é que ha sapatos e sapatos assim como do capacete. Pode ser bom negocio se conheceres/confiares que o material está em muito bom estado. 
